traseu

O suprafață de teren de formă dreptunghiulară este divizată în $N$ fâșii orizontale și $M$ fâșii verticale, de lățimi egale. Se formează astfel $N \times M$ zone de formă pătrată, cu latura egală cu o unitate. Astfel, suprafața este reprezentată sub forma unui tablou bidimensional cu $N$ linii și $M$ coloane, în care pentru fiecare zonă este memorat un număr ce reprezintă altitudinea zonei respective. Interesant este că în tablou apar toate valorile $1, 2, \dots, N \cdot M$. Suprafața este destinată turismului. Deoarece spre laturile de Est și Sud ale suprafeței există peisaje de o frumusețe uimitoare, se dorește găsirea unor trasee turistice în care deplasarea să se realizeze cu pași de lungime unitară mergând doar spre Est și spre Sud. O comisie, care trebuie să rezolve această problemă, a stabilit că un traseu este atractiv dacă și numai dacă ultima poziție a traseului are altitudinea mai mare decât prima poziție a traseului. Un traseu poate începe, respectiv se poate încheia, în oricare dintre zonele terenului, cu respectarea condițiilor anterioare.

Cerință

Se cere să se determine numărul maxim $Z$ de zone pe care le poate avea un traseu atractiv.

Date de intrare

În fişierul de intrare traseu.in se află scrise pe prima linie numerele $N$ şi $M$, cu semnificația din enunț. Pe fiecare dintre următoarele $N$ linii se află scrise câte $M$ numere naturale, reprezentând, elementele tabloului bidimensional precizat în enunț. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spaţiu.

Date de ieșire

În fişierul de ieşire traseu.out se va scrie numărul $Z$, cu semnificația din enunț. Dacă nu există niciun traseu atractiv, atunci se va scrie 0.

Restricții și precizări

• $1 \leq N, M \leq 500$;
• Pentru teste in valoare de $40$ de puncte, $N \leq 50$ și $M \leq 50$.

Exemplul 1

traseu.in

3 4
12 11 10 6
7 5 4 3
9 2 8 1

traseu.out

4

Explicație

• Traseele atractive de lungime $2$ sunt: 7-9, 4-8, 2-8.
• Traseele atractive de lungime $3$ sunt: 5-2-8, 5-4-8.
• Traseele atractive de lungime $4$ (maximă) sunt: 7-5-4-8, 7-5-2-8, 7-9-2-8.

Exemplul 2

traseu.in

3 3
5 8 7
9 6 4
3 1 2

traseu.out

3

Explicație

Traseele atractive de lungime $2$ sunt: 5-8, 5-9, 1-2.
Traseele atractive de lungime $3$ (maximă) sunt: 5-9-6, 5-8-6, 5-8-7.