Un menú es una grilla de \(R \times C\) platos; cada plato tiene un número distinto entre \(1\) y \(R \times C\), que indica el orden en que se quieren comer. Se elige una celda de partida y se camina moviéndose a celdas vecinas (arriba, abajo, izquierda, derecha), pudiendo volver a celdas ya visitadas; cada vez que se entra por primera vez a una celda se come su plato.

Los platos comidos deben ir en orden creciente de número (se pueden saltar números). Calcula la máxima cantidad de platos que se pueden comer.

Equivalentemente: se eligen celdas \(c_1, c_2, \dots, c_k\) con números crecientes, donde cada \(c_j\) con \(j \ge 2\) es vecina de alguna de las celdas \(c_1, \dots, c_{j-1}\); maximiza \(k\).

Entrada

La primera línea tiene dos enteros \(R\) y \(C\) \((1 \le R, C \le 100)\). Siguen \(R\) líneas con \(C\) enteros cada una: los números de los platos, todos distintos entre \(1\) y \(R \times C\).

Salida

Una línea con la máxima cantidad de platos.

Ejemplo 1

Entrada

1 5
5 3 2 1 4

Salida

5

Ejemplo 2

Entrada

1 5
1 5 4 3 2

Salida

4

Ejemplo 3

Entrada

3 3
4 1 3
8 5 9
7 2 6

Salida

6

Regional Latinoamericana 2022 del ICPC, problema I («Italian Calzone & Pasta Corner»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.