După ce ți-ai dat seama că nu poți învinge nici unul dintre monștrii (din problema SAO), ai decis să te retragi și să devii un fermier. Din banii pentru cumpărarea echipamentului ai cumpărat o parcelă codificată sub forma unei matrice de n linii și m coloane, pentru fiecare zonă cunoscându-se fertilitatea ei. Cum nu ai bani ca să cultivi pământul, dorești să selectezi o parcelă în care toate zonele să aibă aceeași fertilitate, iar fertilitatea totală să fie maximă. Fertilitatea totală a unei parcele este egală cu suma fertilităților zonelor care compun acea parcelă.

Cerința

Dându-se matricea codificărilor zonelor din teren, să se determine fertilitatea totală maximă a unei parcele în care toate zonele au aceeași fertilitate.

Date de intrare

Fișierul de intrare sao1.in conține pe prima linie numerele n şi m, iar pe următoarele n linii câte m numere naturale, separate prin spaţii, reprezentând elementele matricei.

Date de ieșire

Fișierul de ieșire sao1.out va conține numărul P, reprezentând fertilitatea totală maximă a unei parcele, în condițiile date.

Restricții și precizări

• 1 ≤ n,m ≤ 500
• fertilitatea totală se va încadra pe tipul de date long long.
• nu există sol infertil (a cărui fertilitate să fie mai mică sau egală cu 0).
• acesta este “bad ending”-ul problemei SAO

Exemplu 1:

sao1.in

4 4
1 1 1 3
1 1 1 3
1 1 1 3
3 3 3 3

sao1.out

21

Explicație

Cele 7 valori de 3 formează zona cu profit maxim.

Exemplu 2:

sao1.in

4 4
3 5 1 3
1 5 5 3
5 5 5 3
3 3 3 3

sao1.out

30

Explicație

Cele 6 valori de 5 formează zona cu profit maxim.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("sao1.in");
ofstream cout("sao1.out");

long long a[501][501], c, f;
int n, m;

void fill(int i, int j){
    c++;
    a[i][j] = 0;
    if(a[i+1][j] == f)
        fill(i+1, j);
    if(a[i-1][j] == f)
        fill(i-1, j);
    if(a[i][j+1] == f)
        fill(i, j+1);
    if(a[i][j-1] == f)
        fill(i, j-1);
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            cin >> a[i][j];

    long long maxi = 0;

    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if(a[i][j] != 0){
                f = a[i][j];
                c = 0;
                fill(i, j);
                if(c * f > maxi)
                    maxi = c * f;
            }

    cout << maxi;

    return 0;
}