ZOJ Problem Set - 3060
Watashi feels bored because he always wins when playing Gongzhu, so he wants to play something different, and he begins to play Evil Game.
In Evil Game, there are M * N grids, each contains a box with a devil or some money. When Watashi gets to a grid, he will open the box at once, and he may get some money or be robbed by the devil a certain amount of money, if Watashi has less money than the devil can rob, his money will become negative representing that he is in debt.
Box in grid (i , j) is represented by mij.
Now Watashi is in the left-top, (0 , 0), and has no money. He wants to get to grid (M - 1 , N - 1) with as much money as he can. Every time, Watashi can move left, right or down.
Now it's your task to calculate the maxmum amount Watashi can get.
There are multiple cases. The first line is a integer T, represents the number of cases.
The first line of each case is two integers M, N, 1 <= M, N <= 100. Then M lines with N integers, -100 <= mij <= 100, in each line representing the grids.
The output for every case is an integer s, represents the maximun amount of money Watashi can take out when he got to (M - 1 , N - 1), s may be negative.
1 2 3 2 -1 3 3 1 -1
Author: LI, Yaochun
Source: ZOJ Monthly, November 2008