FIXED ON Jan 9
After the expansion of Halloween town, people have been complaining. It just takes too long to visit friends now, if all 100,000 households are in a line. After much discussion, Halloween town is rebuilt into a rectangular grid. Now, a conventional trick-or-treat route looks like a box. I.E. people usually choose four numbers, r1, c1, r2, c2, and visit all the houses on row r column c such that:
What should Bob do this year on Halloween?
There will be multiple test cases. First there will be an integer N on its own line, that determines how many test cases there are.
Each test case starts with a line with two integers, r and c (1 <= r, c <= 400), equal to the dimension of Halloween Town. Then, the next r will have c numbers (seperated by spaces) corresponding to the values of the candies handed out by houses on row r. The values are between -100 to 100. At least one household will be giving out non-licorice flavoured candy, and have a positive value
For each test case, output the net benefit of the best "route" Bob can take in a line.
For example, for the input10 | 5 | -3 | -2 | -6 |
0 | 5 | -3 | -2 | 6 |
-6 | -6 | 3 | -2 | 16 |
-4 | 5 | 3 | -2 | 8 |
0 | 5 | -3 | -2 | 6 |
1
5 5
10 5 -3 -2 -6
0 5 -3 -2 6
-6 -6 3 -2 16
-4 5 3 -2 8
0 5 -3 -2 6
37