Diagonal Sum

Given an $N \times N$ size matrix, you have to re-arrange the elements of the matrix in such a way that the difference between the summation of the elements of the main diagonal and the summation of the elements of the secondary diagonal is as large as possible. You can swap between any two elements of the matrix to re-arrange the matrix.

The main diagonal of a matrix consists of those elements that lie on the diagonal that runs from top left to bottom right. And the secondary diagonal of a matrix consists of those elements that lie on the diagonal that runs from top right to bottom left.

Input

In the first line of input, there will be a number $N$ ($3 ≤ N ≤ 100$) as described above. Then there will be $N$ integers in each of the next $N$ lines denoting the matrix. The elements of the matrix will lie in the range $[-10^6,10^6]$. In other words, the absolute value of each element of the matrix will not exceed $10^6$.

Output

In a single line, print the maximum possible difference between the summation of the elements of the main diagonal and the summation of the elements of the secondary diagonal after re-arranging.

Sample

Input	Output
3 -11 5 8 2 6 17 4 -3 2	39
We can re-arrange the matrix to: 17 5 -11 2 6 4 -3 2 8 The difference is $(17+6+8) - (-11+6-3) = 39$, which is the maximum in this case.