CareerCup

Hi..can anyone give test case for the following question where alice wins other than when m=1,n=1...
Alice and Bob have come to spend their day in a FunFair which is close to their house. They have played almost all games and seen all the attractions. But there's one game left which has caught their attention. The winner of this game could get a LOT of candies! The game is as follows:
The game is a two-player game which is played on an NxM grid.

Each cell of the grid has a certain number of candies. A[i][j] denotes the number of candies in the jth column of the ith row.

The players make alternate turns.

In each turn, a player must remove one complete row or one complete column from the grid. He will add all the candies in that row/column into his account.

The only possible rows that a player can remove in his/her turn are the top row or the bottom row. Similarly, only leftmost column or the rightmost column can be removed in one turn.

After removing the row or column, the game is played on the new reduced grid with one less row or column respectively.

When the entire matrix is emptied, the player with higher number of candies wins the game and can take all those candies with him/her. The loser has to give back the candies collected so far and return empty-handed.

If both players have equal number of candies, both of them are declared winners.

Alice and Bob want to take as many candies home as possible. They don't have much time with themselves. So they come up with a strategy using which they want to increase Bob's share of candies and decrease Alice's share. This way, they plan to make Bob win and take his entire share of candies! The strategy is as follows:
Alice decides to pick the row or column from the present grid which has the least number of candies in every turn of hers.

If there are more than one such options, then her order of preference will be:
1) first row
2) last row
3) first column
4) last column.
For example, if all these 4 rows/columns have the same number of candies, she will remove the first row in this turn.

Bob chooses an optimal strategy through which he maximizes his share of candies in the end of the game. Note that Bob's strategy maximizes the number of his candies, not winner's candies. Also note that Bob knows Alice's strategy, of course, and he will take into account her strategy when he decides his move.

It's quite evident that their strategy is not optimal. It might happen that Bob loses a game. And sometimes, both might win (with equal number of candies). Given the grid and the number of candies in each cell, your task is to tell them how many candies will the winner get if they play with this combined strategy. Alice will always start the game (Ladies first!).
Input:

First line of the test data contains a single integer T, the number of test cases.
Each test case starts with two space separated integers N and M, the number of rows and columns of the grid respectively.
Then follow N lines containing M space separated integers A[i][j]. These lines describe the grid.
Output:

For each test case, output a single line containing the number of candies the winner(s) gets.
Constraints:

1 ≤ T ≤ 25
1 ≤ N, M ≤ 50
0 ≤ A[i][j] ≤ 1000000000


Example:

Input:
3
3 3
0 9 9
0 6 6
0 9 6
2 2
1 1
1 1
1 4
1 2 3 4

Output:
39
4
9