Due to do his good deeds, Krishna asked Bheem for a wish. As we know our friend Bheem likes laddus very much so he wished that he wanted to be in a world full of tasty laddus. So, Krishna with his magic sent Bheem to a magical world full of laddus. In this magical world even laddus where magical. There Bheem found that enery that he can gain eating some of the laddus increases every day and those special laddus were placed in a N x M rectangular grid, each cell E[i][j] (1 d^th day gives enery equal to d * E[i][j] where E[i][j] is the enery of laddu in the cell (i,j) that can be gained by eating on day 1.
Each day Bheem can only eat all laddus of leftmost column, rightmost column, topmost row or bottommost row of the grid. Help Bheem maximize the overall enery gained by eating the laddus if he starts eating them on day 1.

 

Input

• First line of each test case contains two space separated integers N and M. Then N lines follows, each of which contains M space separated integers representing the initial eanery that can be gained by eating the laddus.

 

Output

• For each test case output a single number denoting the maximum enery that can be gained by eating the laddus.

 

Constraints

• 1 = T = 50
• 1 = N,M = 32
• 1 = E[i][j] = 10^9

 

Example

Input: 1 2 2 1 2 3 4 Output: 21

Explanation

Example case 1. Initially the grid representing the laddus is : {{1,2},{3,4}}.
Bheem will gain optimal energy, when he will eat the laddus in following order.
On 1st day Bheem eats all laddus of 1st row (topmost row).
Energy gained by Bheem on 1st day = 1+2 = 3
The resultant grid becomes {{3,4}}.
On 2nd day Bheem eats all laddus of 1st column (leftmost column).
Energy gained by Bheem on 2nd day = 2*3 = 6.
The resultant grid becomes {{4}} (there is only 1 element).
On 3rd day Bheem eats the only laddu.
Energy gained by Bheem on 3rd day = 3*4 = 12.
Therefore, the total energy gained by Bheem after eating all the laddus = 3 + 6 + 12 = 21.