DA-IICT Intra Programming Contest 07

Given a floor covered with r x c square tiles.  where there are r rows of tiles from front (first row) to back (last row) and c columns of tiles from left to right.Each tile has 1 to 100 stones on it. You task is to grab as many stones as possible, subject to following restrictions:
1) Start from 1x1 and collect as many stones as possible and reach at r x c grid.
2) You can move either right to the tile, or below to the tile or diagonally to the right.
Given the values of r and c, and the number of stones on each tile, write a program to compute the maximum possible number of stones You can grab in one single trip from 1x1 tile to the rxc tile.

Input:
First line consist of a single integer t, the number of test cases (1<=t<=100). In each test cases, the first line has two integer . The first integer r (1<=r<=100) is the number of rows of tiles on the floor. The second integer c (1<=c<=100) is the number of columns of tiles on the floor. Next, there are r lines of inputs. The ith line of these, specifies the number of stones in each tile of the ith row from the front. Each line has c integers, where each integer m (0<=m<=100) is the number of stones on that tile. The integers are separated by a space character.

Output:
Output the maximum number of stone you can collect.


Input:
2
4 4
1 2 3 4
1 2 3 4
4 3 2 1
4 3 2 1
2 2
1 2
2 1

Output:

16
4