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 x 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, …, N•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ța

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 ≤ N ≤ 500
• 1 ≤ M ≤ 500
• Pentru teste în valoare de 40 de puncte, N ≤ 50.
• În concurs s-au acordat 10 puncte din oficiu. Aici s-au acordat pentru exemplele din enunț.

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.

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 x 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, …, N•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ța

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 ≤ N ≤ 500
• 1 ≤ M ≤ 500
• Pentru teste în valoare de 40 de puncte, N ≤ 50.
• În concurs s-au acordat 10 puncte din oficiu. Aici s-au acordat pentru exemplele din enunț.

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.

#include <bits/stdc++.h>





using namespace std;

const static int kMaxN = 1000;

int main() {
    ifstream cin("traseu.in");
    ofstream cout("traseu.out");

    int N, M; assert(cin >> N >> M);
    assert(1 <= N && N <= kMaxN);
    assert(1 <= M && M <= kMaxN);

    vector< pair<int, int> > pos(N * M, make_pair(-1, -1));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j) {
            int x; assert(cin >> x);
            assert(1 <= x && x <= N * M);
            --x;
            assert(pos[x] == make_pair(-1, -1));
            pos[x] = make_pair(i, j);
        }

    vector<int> best(N, M);
    int answer = -1;
    for (int i = 0; i < N * M; ++i) {
        int x, y; tie(x, y) = pos[i];
        for (int j = 0; j <= x; ++j)
            if (best[j] <= y)
                answer = max(answer, x - j + y - best[j]);

        best[x] = min(best[x], y);
    }

    cout << answer + 1 << "\n";
}