El monstruo y el gato.
El gato de uno de los azucareros del centro quiere escapar de su enemigo mortal: el monstruso Urón. Actualmente está atrapado en una mesa cuadrada (tablero en lo adelante) de llena de comida colocada por Urón para retrasar la fuga del gato. Las filas del tablero están numeradas con los números del al , las columnas están numeradas con los números del al y el gato se ubica inicialmente en la celda . La comida colocada en la celda tiene placer para el gato, y es posible que algunos alimentos traigan placer negativo. Cuando el gato está en una celda, siempre come la comida que hay en ella.
Dado que el monstruo parte de una posición al noroeste del gato, el gato se mueve en dirección sureste. Esto significa que si actualmente está en la celda , puede saltar de la mesa para escapar de la trampa o saltar a una de las celdas al sureste de . Específicamente, puede saltar a celdas con números para las cuales y . El gato intentará escapar de la mesa habiendo maximizado el placer experimentado.
Por lo tanto, escriba un programa que, para cada posible celda inicial , encuentre el máximo placer que el gato puede experimentar mientras huye del monstruo y se mueve de acuerdo con las reglas descritas. Para poner a prueba tus habilidades (y no mirar un montón de números), el gato sólo te pide la suma de estos números.
Entrada
Los números naturales y se ingresan desde la primera línea de la entrada estándar: el número de filas y columnas del tablero. De cada una de las siguientes filas, aparecen enteros que son los placeres de la comida a la fila correspondiente.
Salida
Genera un solo número: la suma máxima de los placeres antes del escape del gato para cada posible celda inicial .
Restricciones
Ejemplo de Entrada
4 3
1 2 3
-2 -3 0
-1 4 -2
3 -1 -1
Ejemplo de Salida
25
La siguiente tabla muestra los placeres máximos si el gato parte de cada celda:
7 6 3
2 1 0
3 4 -2
3 -1 -1
Para lograr el máximo placer, comenzando desde la celda , el camino del gato debe ser: , luego salta de la mesa y de la trampa. El placer acumulado será .
Comments