Rezolvare PBinfo #2741

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 parcelelor și 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.