Después de ganar todas las competiciones de informática en el mundo, Peter el Hacker decidió enfrentarse a un nuevo reto. El se registró en un sitio web de Rusia para la competencia en línea de criptografía y cerrajería “VerhShifr” y tan pronto como el arribó a Moscu participó en las finales.

Durante una de las excursiones que los organizadores prepararon, el grupo visitó un amplio museo dedicado a las muñecas Matryoshka – tradicional juguete ruso. Dentro del museo, había un extraño laberinto. Sus habitaciones y el laberinto mismo eran cuadradas y sus paredes estaban paralelas a los ejes norte-sur y este-oeste. Cada habitación tenía cuatro puertas – una en cada lado. La entrada al laberinto estaba en la habitación más al noroeste y la salida en la más al sureste.

El equipo nacional ruso en cifrado preparó un interesante juego para sus oponentes. En cada habitación, ellos dejaron una muñeca Matryoshka simple y vacía con tamaño único. Todo el mundo tenía que ir a través del laberinto y recoger tantos juguetes como fuera posible pero bajo una condición. Cada vez que uno coja una muñeca, tiene que anidar todas las muñecas que tiene dentro de la nueva muñeca. Por supuesto, los concursantes pueden decidir si coger una Matryoshka (si es más grande que la última) o continuar hacia la próxima habitación. Para hacer las cosas aun más duras, el genio de las cajas fuertes – Metr Pitrichev – ha modificado las puertas tal que de una habitación a otra uno puede moverse solamente a las habitaciones al sur y al este.

Peter el Hacker, por supuesto, no es un maestro con las cerraduras y no puede tratar con la modificación. En cambio, el escribió un programa, el cual puede encontrar la mejor manera para recoger tantos juguetes como sea posible. Puede usted hacer esto, también? Escriba un programa que calcule la cantidad máxima de muñecas Matryoshka, que Peter el Hacker puede recoger para una configuración dada de las habitaciones.

Entrada

La entrada contiene en la primera línea un entero ~N (1<N<1000)~, seguido por ~N~ filas con ~N~ números (uno por cada habitación) cada una. Cada número describe el tamaño del juguete dentro de la correspondiente habitación. Las filas están ordenadas de norte a sur (la primera fila está más al norte) y las columnas están ordenadas de oeste a este (el primer número de cada fila es el número que esta más al oeste). Una muñeca Matryoshka se acomoda dentro de otra si esta tiene un tamaño más pequeño que la segunda muñeca. Los tamaños serán números en el rango ~[1, N^2]~ y no se repetirán.

Salida

La salida contiene un entero simple – la cantidad máxima de juguetes que Peter el Hacker puede recolectar siguiendo las reglas.

Ejemplo #1 de Entrada

3
9 4 1
6 5 7
2 3 8

Ejemplo #1 de Salida

4

Ejemplo #2 de Entrada

4
1 15 4 5
2 10 9 16
14 7 8 3
13 6 11 12

Ejemplo #2 de Salida

6