Preparing NOJ

GRID

2500ms 65536K

Description:

I think most ACMers are familiar with grid map.
In a grid map. Each grid has its own value vij.
At the beginning you are on (0,0) and you have to go to (M,N)
You have two ways to move (0,1) and (1,0)
(0,1) means when you stand on(x,y) you move to (x,y+1)
(1,0) means when you stand on(x,y) you move to (x+1,y)
Now you have to find a way from (0,0) to (M,N) to make the combined value of all the grid you have passed is the largest.
Output the maximum combined value.

Input:

In the first line there is an integer T. means there are T cases.
In the first line of each case there are 2 integers M,N<1000.
On the following M line each line has N integers;
The yth number on the ith line is vij <5000, which represents the value of grid (i,j).

Output:

For each case you only to print an integer in a single line. The integer is the maximum combined value of the grids you have passed.

Sample Input:

1
1 1
1

Sample Output:

1

Note:

null

本题由旧版NOJ导入,来源:3E

Info

NOJ

Provider NOJ

Code NOJ1998

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet