El Granjero Juan quiere tomar una foto de sus vacas pasteando en su pastizal para colgar en su pared. El pastizal está representado por una cuadrícula ~N~ por ~N~ de celdas cuadradas (piense en un tablero de ajedrez ~N.N~), con ~2 \le N \le 1000~.

En la última foto que tomó el Granjero Juan, sus vacas estaban muy amontonadas en una región del pastizal. Esta vez, él quiere asegurarse de que sus vacas están repartidas apropiadamente en el pastizal. El por lo tanto insiste en las siguientes reglas:

. No pueden ser puestas dos vacas en la misma celda. . Cada subcuadrícula de ~2 x 2~ celdas (~(N-1) x (N-1)~ de ellas en total) debe contener exactamente 2 vacas.

Por ejemplo, está disposición es válida:

CCC
...
CCC

En cambio esta disposición no lo es, debido a que la región cuadrada ~2x2~

que contiene la esquina inferior derecha contiene solamente 1 vaca:

C.C
.C. 
C..

No hay otras restricciones. Usted puede asumir que el Granjero Juan tiene un número infinito de vacas disponble (basados en la experiencia anterior, asumir esto parece ser ciertamente correcto.)

El Granjero Juan prefiere que algunas celdas contengan vacas más qu eotras. En particular, cree que cuando una vaca es puesta en la celda ~(i,j)~, la belleza de la foto se aumenta en ~a_{ij}~ ~(0 \le a_{ij} \le 1000)~ unidades.

Determine la belleza máxima total posible de una disposición válida de vacas.

Entrada

. La primera línea contiene ~N~ . Cada una de las siguientes ~N~ líneas contiene N enteros. El entero j ésimo de la fila i ésima desde arriba es el valor de ~a_{ij}~

Salida

Imprima un entero dando la belleza máxima posible de la foto resultante.

Ejemplo de Entrada

4
3 3 1 1
1 1 3 1
3 3 1 1
1 1 3 3

Ejemplo de Salida

22

En este ejemplo, la belleza máxima puede ser lograda con la siguiente disposición:

CC..
..CC
CC..
..CC

La belleza de esta disposición es ~3+3+3+1+3+3+3+3=22~