Greedy Grid Game

Limits 1s, 512 MB

“Uban game world” is an indoor gaming zone. It offers 55 game segments for only one ticket. Today, Aliban is going to participate in one of the games called “Greedy Grid Game”.

This game is about an n×mn×m grid. Each cell contains an integer value ai,ja_{i,j}. Here ai,ja_{i,j} denotes the number in the ithi^{th} row from the top and jthj^{th} column from the left. Aliban has to start the journey from (1,1)(1,1) and finish at (n,m)(n,m). She can’t move any cell as she pleases. There are some rules that follows -

  1. If she starts her movement by going right, i.e., (i,j)(i,j) to (i,j+1)(i,j+1), then she is not allowed to stop until she reaches the border cell (i,m)(i,m) of the grid.

  2. If she starts her movement by going down, i.e., (i,j)(i,j) to (i+1,j)(i+1,j), then she is not allowed to stop until she reaches the border (n,j)(n,j) cell of the grid.

  3. She is allowed to give at most one diagonal move in her whole journey. For example, (i,j)(i,j) to (i+1,j+1)(i+1,j+1), (i,j)(i,j) to (i+1,j1)(i+1,j-1), (i,j)(i,j) to (i1,j+1)(i-1,j+1), (i,j)(i,j) to (i1,j1)(i-1,j-1).

  4. She is not allowed to visit any cell more than once.

  5. Except for the diagonal moves, she cannot move left or up.

  6. She can not move outside of the grid.

The score of Aliban will be the sum of cell values she visits throughout her journey.

As Aliban is not an expert in calculation she asks for your help. You have to find the maximum score she can achieve without violating any rules.


The input consists of multiple test cases. The first line contains an integer t(1t100)t (1≤t≤100)  — the number of test cases. The description of the tt test cases follows.

The first line of each test case contains two positive integers nn and mm(1n,m105;1nm105)(1≤n,m≤10^5; 1≤nm≤10^5)— the number of rows and columns respectively.

The following nn lines contain mm integers each, the jthj^{th} element in the ithi^{th} line holds the value ai,ja_{i,j} (106ai,j106)(-10^6≤a_{i,j}≤10^6).

It is guaranteed that the sum of nmnm over all test cases does not exceed 10510^5.


For each test case, print the maximum score Aliban can achieve.


3 3
1 2 2
1 10 -2
2 -3 1
3 3
-1 2 3
-4 5 6
10 2 3

In the first test case, to achieve the best score her movement should be (1,1)(1,2)(1,3)(2,2)(2,3)(3,3)(1,1)→(1,2)→(1,3)→(2,2)→(2,3)→(3,3)