Back to Category
d243: [12.06] D - Taking Money
Keyword:

Difficulity: N/A | Test Data Sets: 1 (Hidden) | Judging: Traditional Judge
Accepted : 1 Times | Submit :1 Times | Clicks : 408
Accepted : 1 Users | Submit : 1 Users | Accepted rate : 100%
Time Limit :3000 ms | Memory Limit : 64000 KBytes
Update : 2012-10-29 17:20

Content:

Two viruses found many cells, arranged as an M-by-N matrix S. Each cell may have some mysterious resource. We de ne the cell S11 as the starting cell, and the cell SMN as the ending cell. The two viruses traverse from the starting cell to the ending cell separately, taking all of the resource inside the cell they traversed. Now de ne the maximum amount resource they can collected as R. Can you tell us the value of R?
 
Note that if a cell Sij is traversed by a virus, the other virus still can traverse to Sij but the resource is already collected. You should not count the collected resource twice in this situation.
 
 

Technical Speci cation

  •  1 ≤ M,N ≤ 100
  •  0 ≤ Sij ≤ 100 

Input:

There are multiple test cases in the input. Each test case starts with a line containing two numbers M and N. Then followed with M lines, containing N numbers. The j-th number in i-th line of these M lines stand for the amount of resource of the cell Sij.
 
 

Output:

For each test case, output R in a line.

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3 2
2 3
4 5
6 7
4 4
1 2 3 4
4 1 1 1
4 4 4 1
1 1 4 1

Sample Output :

27
33

Hint :

click here to download the problem solving hint

Author :


  Solve it!   Status Forum

C
C++
JAVA
PASCAL
50757. rabbit125
(2s, 14268KB, 2102B)

Program running time may be affected by various factors. Check server system environment information here