RoGN1 P78428

El robot ro-GN1 (“Roñi”, para los amigos), originalmente diseñado para recoger restos de naufragios (joyas, monedas de oro, etc.), tuvo un accidente que le inutilizó el motor izquierdo. El robot puede desplazarse hacia arriba, hacia abajo, y hacia la derecha, pero nunca más podrá moverse a la izquierda, porque hace tiempo que dejaron de fabricarse piezas de recambio para reparar su lesión.

Sus nuevos amos lo usan ahora para limpiar el fondo de la piscina de un parque acuático, donde pasa largos días recogiendo la basura que dejan los niños. Sin embargo, Roñi fue programado para hacer su trabajo impecablemente: ayúdale a conseguirlo.

La base de la piscina es un rectángulo de $n$ por $m$ baldosas. En cada baldosa se encuentra una cierta cantidad de basura, que Roñi recogerá si pasa por encima de ella. Roñi no puede desplazarse hacia la izquierda, pero puede moverse arriba, abajo y a la derecha tantas veces como sea necesario. Deberás tener en cuenta que algunas baldosas están tan sucias que Roñi no puede ni limpiarlas ni cruzarlas, por temor a dañarse aún más. ?‘Cuál es la cantidad máxima de basura que Roñi puede recoger?

Entrada

La entrada consiste de un número indeterminado de casos de prueba. Cada caso de pruebas empieza con una línea con tres números $n>0$, $m>0$ y $k>1$, que son las dimensiones $n\times m$ de la piscina y la máxima cantidad $k$ de basura que puede tener una baldosa para que Roñi pueda pasar por encima suyo (y limpiarla en el proceso). A continuación, vienen $n$ líneas con $m$ números naturales cada una, describiendo la cantidad de basura que hay en cada baldosa. Únicamente habrá una casilla con $0$ unidades de basura: aquella en la que se encuentra actualmente Roñi. Entre dos casos de prueba hay una línea en blanco.

Se te garantiza que ninguna entrada contendrá más de 100 casos de prueba, que ninguna baldosa tendrá más de 1000 unidades de basura, y que $n,m\le 200$.

Salida

Para cada caso de pruebas, escribe la cantidad máxima de basura que Roñi puede recoger.

Puntuación

• Test1:

  Resolver entradas con casos de prueba donde ninguna baldosa estará tan sucia que Roñi no pueda cruzarla, como el ejemplo 1.

• Test2:

  Resolver entradas con casos de prueba con $n=2$ filas y $m\leq 40$ columnas, como el ejemplo 2.

• Test3:

  Resolver entradas con casos de prueba con $n=2$ y $n=3$ filas y $m\leq 40$ columnas, como el ejemplo 3.

• Test4:

  Resolver entradas con casos de prueba con $n,m \leq 40$, como el ejemplo 4.

• Test5:

  Resolver entradas con no más de 20 casos de prueba con $n,m\leq 200$.