Shuai often plays a matrix game with his classmates: for a given matrix, each element in the matrix is a non-negative integer. The rules of the game are as follows:
Each step, one must remove one element from each row each time, for a total of numbers removed. After times, all elements of the matrix are removed;
Each element removed each time can only be the beginning or end of a line;
Each removal has a score value, which is the sum of the scores of the number removed in the rows. These scores are the value of the element to be removed times , where represents the -th removal (starting from );
- The total score at the end of the game is the sum of the scores obtained from the times' removal.
Shuai would like to ask you to help write a program, for any matrix, you can find the maximum score after the game.
Input Specification
- Line contains two integers and .
- Lines contain the matrix, where each line has non-negative integers separated by a single space each.
Output Specification
One intger, the maximum score.
Sample Input 1
2 3
1 2 3
3 4 2
Sample Output 1
82
Explanation of Sample 1
- The first time: the first element is taken from the first line, and the last element is taken from the second line. This time the score is
- The second time: take the first element of both lines, this time the score is
- Third time: score is . The total score is .
Sample Input 2
1 4
4 5 0 5
Sample Output 2
122
Sample Input 3
2 10
96 56 54 46 86 12 23 88 80 43
16 95 18 29 30 53 88 83 64 67
Sample Output 3
316994
Constraints
of the data satisfy , answer does not exceed .
of the data satisfy , .
Comments