Problema número 697

Espiral galáctica

Tiempo máximo: 1,000-2,000 sMemoria máxima: 4096 KiB
Una galaxia en el firmamento

Nuestra galaxia, la Vía Láctea, tiene forma de espiral. Se estima que hay entre cien mil y cuatrocientos mil millones de estrellas en ella.

No te asustes, que no te vamos a mandar contarlas todas una a una. Resulta que hemos inventado un artilugio que, al enfocarlo al cielo, nos divide la porción de firmamento que vemos en casillas y nos cuenta las estrellas que hay en cada una de ellas. El artilugio se puede regular y podemos elegir el tamaño de la zona de cielo a examinar. Eso sí, esa zona siempre ha de ser cuadrada y con el lado de longitud impar.

Solo nos falta programarlo para que sea capaz de contar las estrellas que pertenecen a nuestra galaxia, es decir, las que están en la espiral. La espiral siempre comienza en la casilla central y sus brazos van avanzando y creciendo en la dirección de las agujas del reloj (arriba, derecha, abajo, izquierda).

Por ejemplo, supongamos que estamos viendo una porción de firmamento con lado de tamaño 5. Esta porción está dividida en 25 casillas y tenemos anotadas la cantidad de estrellas que hay en cada una de ellas. En la siguiente figura, a la izquierda, las casillas correspondientes a la espiral aparecen resaltadas en amarillo, y en total suman 41 estrellas.

Galaxia de lado 5

En la figura a la derecha aparece una porción con lado de tamaño 7, dividida en 49 casillas. En este caso las estrellas de la espiral son 54.

Entrada

Cada caso de prueba son varias líneas.

La primera es un número N impar y menor que 100, que indica el tamaño del lado de la porción del universo que estamos viendo. Recuerda que esta porción siempre es un cuadrado. A continuación, aparecen N líneas, cada una con N números entre 0 y 100.000 y separados por espacios, indicando el número de estrellas que se ven en cada casilla.

El último caso de prueba tiene N igual a 0 y no se debe procesar.

Salida

Para cada caso de prueba el programa escribirá el número de estrellas que pueden verse en la espiral galáctica.

Entrada de ejemplo

3
3 3 4
2 2 7
1 3 5
5
2 4 4 4 4
2 3 3 4 5
5 2 2 7 1
2 1 3 5 3
2 4 3 1 2
7
2 1 2 2 3 2 3
4 2 4 4 4 4 4
3 2 3 3 4 5 3
4 5 2 2 7 1 2
5 2 1 3 5 3 6
4 2 4 3 1 2 0
3 9 9 9 9 2 9
0

Salida de ejemplo

9
41
54