Imagina la sorpresa de Bessie al ver a un leprechaun saltando por el pasto norte. No es ninguna tonta: se lanzó y lo atrapó con sus pezuñas prensiles.
«Un deseo, bovina. Es todo lo que tengo para vacas», dijo.
«Riquezas», dijo Bessie soñadora. «La oportunidad de obtener riquezas».
Los leprechauns nunca conceden los deseos de sus captores del modo más fácil. Al despejarse el humo de una fuerte explosión, un donut brillante giraba lentamente sobre campos verdes.
«Te hice un toro», dijo suavemente. «Sobre él hay una matriz $N\times N$ $(1 \le N \le 200)$ de enteros en $-1{,}000{,}000,\ldots,1{,}000{,}000$ que determina tu riqueza. Entre todas las secuencias del toro debes hallar una secuencia de enteros contiguos en una misma fila, columna o diagonal cuya suma sea máxima».
Bessie pensó y entendió que el toro hace «volver» las columnas, filas y diagonales, permitiendo elegir elementos contiguos que rodean el borde lateral o superior.
Bessie te dará la matriz. Halla la mayor suma posible, eligiendo al menos un elemento.
Como ejemplo, la matriz $4\times4$ izquierda de abajo marca todos los elementos de una diagonal que rodea el borde:
8 6 6* 1 8 6* 6 1
-3 4 0 5* -3 4 0 5
4* 2 1 9 4 2 1 9*
1 -9* 9 -2 1 -9 9*-2La diagonal marcada a la derecha contiene dos nueves (el número más alto) y un seis, suma 24. Es la mejor suma y usa solo tres de los cuatro elementos posibles de la diagonal.
Entrada
- Línea 1: un entero $N$.
- Líneas $2,\ldots,N+1$: la línea $i+1$ contiene $N$ enteros separados por espacios formando la fila $i$.
Salida
- Línea 1: un entero, la mayor suma según las reglas anteriores.
Ejemplos
Entrada 1
4 8 6 6 1 -3 4 0 5 4 2 1 9 1 -9 9 -2
Salida 1
24
Fuente del problema: adaptado de BOI'98, 2008