Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
72 - ZOJ Monthly, November 2008 - E
Evil Game

Time Limit: 1 Second      Memory Limit: 32768 KB

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.

  • If mij > 0, then mij money is in the box. After Watashi takes the money and left, a devil appeares, and when he gets to this grid next time, the devil will rob mij money from him.
  • If mij < 0, then each time Watashi gets to this grid, he will be robbed by the devil, and lost -mij money.
  • If mij = 0, then the box is empty, neither can Watashi get money nor will be robbed when he arrived there.

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.

Input

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.

Output

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.

Sample Input

1
2 3
2 -1 3
3 1 -1

Sample Output

5

Author: LI, Yaochun
Submit    Status