Uno de los campos del granjero Juan es particularmente montanosa, y el quiere comprar un nuevo tractor para conducir alrededor de el. El campo es descrito como una grilla de \(N×N\) elevaciones conformadas enteros positivos ~(1 \leq N \leq 500)~. Un tractor capaz de moverse desde una celda a una celda adyacene (un paso al norte, este, sur u oeste) con un peso de diferencia ~D~ cuesta exactamente ~D~ unidades de dinero.

Al granjero Juan le gustaria pagar suficiente por su tractor tal que, empezando por alguna celda en su campo, el pueda satisfactoriamente conducir el tractor alrededor para visitar al menos la mitad de las celdas en el campo (si el numero total de celdas en el campo es impar, el quiere visitar al menos la mitad de las celdas redondeadas).

Por favor, ayude al granjero Juan a computar el mínimo costo necesario para comprar un tractor capaz de cumplir su tarea.

Entrada

Una línea con un solo número entero, el valor de ~N~.

~N~ líneas cada una conteniendo ~N~ enteros positivos separados por espacios (cada uno menor que un millón) especificando una fila en el campo del granjero Juan.

Salida

Una linea conteniendo el costo mínimo del tractor que es capaz de moverse al menos por la mitad del campo del granjero Juan.

Ejemplo de Entrada

5
0 0 0 3 3
0 0 0 0 3
0 9 9 3 3
9 9 9 3 3
9 9 9 9 3

Ejemplo de Salida

3

Explicación del ejemplo: El granjero Juan tiene un campo de 5×5 celdas. Las elevaciones de la primera fila son 0, 0, 0, 3 y 3, y asi sucesivamente.

Un tractor con costo 3 es capaz de moverse entre elevaciones de tamaño 0 y elevaciones de tamaño 3. Todos los bloques de celdas con tamaño 0 y 3 componen, juntos, al menos la mitad del campo del granjero Juan.