Genie is given an $n \times n$ grid of integers $E_{ij}$, where $E_{ij}$ can be negative.
A diamond is defined as a set of cells $(x_i \pm d, y_i)$, $(x_i, y_i \pm d)$, and all intermediate cells forming a diamond shape around the center $(i, j)$ with $d \le r$, where $r$ is the radius of the diamond.
Genie must find the maximum sum of the value of any such diamond shape that fits entirely within the grid. At least one cell must be selected.
The first line of input contains an integer $n\ (1 \le n \le 100)$ — the dimension of the matrix.
The next $n$ lines contain $n$ integers $E_{ij}\ (-10^9 \le E_{ij} \le 10^9)$ — the values of the grid.
Output a single integer, denoting the maximum sum value of any diamond shape within the grid.
Input:
2 1 2 3 4
Output:
4
Input:
3 -10 5 -50 26 -1 10 0 6 45
Output:
46