Laberinto diáfano
La literatura científica está llena de investigaciones realizadas con ratones en las que se pone al sacrificado animal con un montón de electrodos en un laberinto y se le cronometra para ver cuánto tiempo tarda en llegar a la comida.
Cuando Juani Males empezó sus estudios de doctorado a nadie le extrañó, teniendo en cuenta sus años de voluntariado en protectoras de animales, que se opusiera a hacer experimentos de ese tipo. Tras muchas semanas de pensar cómo podría medir la inteligencia de los roedores sin meterles en estrechos pasillos, ha diseñado un experimento que resulta difícil incluso a humanos.
El experimento tiene lugar también en un entorno cerrado, en concreto en un espacio rectangular dividido en casillas. Al contrario de lo que ocurre con los laberintos, eso sí, entre dos casillas no hay muros, por lo que es un espacio diáfano en el que se puede ir de una celda a cualquiera de sus adyacentes en horizontal o vertical. Para medir la inteligencia, en cada celda ha colocado una cantidad de comida y el ratón debe ir desde la esquina superior izquierda a la inferior derecha cogiendo toda la comida que pueda (incluida la de esas dos esquinas). La única condición que debe cumplir el ratón es no pasar dos o más veces por la misma celda, pues se activarían unas trampas que disparan chorros de agua. ¡Juani no quiere ser muy dura tampoco con los castigos!
¿Qué cantidad de comida podrá conseguir el ratón como máximo?
Entrada
Cada caso de prueba está formado por varias líneas. La primera contiene el tamaño del entorno en dos números, Tx y Ty (entre 1 y 100) con el número de columnas y filas.
A continuación vienen Ty líneas con Tx números cada una indicando la cantidad de comida de cada celda. La comida total del entorno no excederá 109, pues los ratones perderían el interés por ella.
Tras el último caso de prueba viene una línea con dos ceros que no debe procesarse.
Salida
Por cada caso de prueba se escribirá una única línea con la cantidad máxima de comida que el ratón puede conseguir teniendo en cuenta que se puede mover en horizontal o vertical pero no puede pasar dos veces por el mismo sitio.
Entrada de ejemplo
2 2 8 8 2 8 3 2 0 2 2 2 2 0 0 0
Salida de ejemplo
24 8