Halloween Squared - Challenge Problem

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?

INPUT

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

OUTPUT

For each test case, output the net benefit of the best "route" Bob can take in a line.

SAMPLE INPUT

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

SAMPLE OUTPUT

37