Din cauza blestemelor dușmanilor, asupra plantației de ‘noledge a vrăjitorului Arpsod s-a năpustit o ploaie de…meteoriți. Plantația vrăjitorului e foarte bine delimitată: aceasta are forma unei matrice cu N linii și M coloane, iar în fiecare celulă era plantat câte un fir de ‘noledge. Din motive clare de răzbunare, dușmanii nu s-au mulțumit cu o singură ploaie, astfel, pe plantația vrăjitorului au căzut meteoriți în mai multe reprize. La fiecare repriză, pe fiecare celulă a unui dreptunghi bine delimitat, au căzut exact C meteoriți. După ce ploaia s-a oprit, pe fiecare celulă se afla un “bloc” de piatră de înălțime egală cu numărul meteoriților căzuți în acea celulă. Arpsod, foarte furios, a luat următoarea decizie: va construi un laborator exact peste meteoriții căzuți, de unde își va pedepsi dușmanii. El a hotărât că cel mai bun amplasament pentru acest laborator este la înălțime maximă. Totodată, el își dorește ca laboratorul lui să aibă o suprafață cât mai mare.

Cerința

Deoarece Arpsod şi arhitectul său, Ierdnac, sunt prea ocupaţi să pregătească schița viitorului laborator, vă roagă pe voi să determinați aria maximă a unei suprafețe cu celule învecinate, de înălțime maximă precum și numărul de fire de ‘noledge rămase neatinse după căderea meteoriților ( poate au ratat vreunu’ ! ).

Date de intrare

Pe prima linie a fișierului meteoriti.in se află trei numere naturale separate prin spațiu: N și M, reprezentând dimensiunile plantației și R, reprezentând numărul de reprize de meteoriți. Pe următoarele R linii se vor afla cinci valori separate prin spațiu: r1 c1 r2 c2 C, unde r1 c1 reprezintă coordonatele colțului stânga sus ( linie coloană ) iar r2 c2 coordonatele colțului dreapta jos ( linie coloană ) ale dreptiunghiului pe care vor cădea meteoriți iar C reprezintă numărul de meteoriți ce vor cădea pe fiecare celulă din cele delimitate.

Date de ieșire

În fișierul meteoriti.out se va scrie, pe o singură linie, separate prin spațiu, aria maximă a unei suprafețe de înălțime maximă, formată numai din celule vecine respectiv numărul de fire de ‘noledge neafectate de meteoriți.

Restricții și precizări

• 4 ≤ N, M ≤ 2.000
• 1 ≤ R ≤ 100.000
• 1 ≤ r1 ≤ r2 ≤ N
• 1 ≤ c1 ≤ c2 ≤ M
• 1 ≤ C ≤ 20.000
• Două celule se consideră vecine dacă au cel puțin o latură comună.
• Înălțimea inițială a celulelor se consideră 0.
• Se garantează că pentru 30% din teste 4 ≤ N, M ≤ 300 și 1 ≤ R ≤ 300
• Pentru rezolvarea corectă a primei cerinţe se acordă 80% din punctajul pe testul respectiv iar pentru rezolvarea corectă a celei de-a doua cerinţe se acordă 20% din punctajul pe testul respectiv
• Fișierul de ieșire TREBUIE să conțină exact DOUĂ valori chiar dacă doriți să rezolvați o singură cerință din cele două
• Dacă îi veți da răspunsul corect vrăjitorului, acesta vă va primi și pe voi prin laboratorul său.
• NU este bine să îl supărați pe vrăjitor!

Exemplu

meteoriti.in

5 6 7
2 2 4 3 1
4 4 4 6 2
1 5 4 6 1
2 5 3 6 1
2 3 4 3 1
5 1 5 3 3
4 2 4 2 1

meteoriti.out

3 12

Explicație

Matricea după meteoriţi:
0 0 0 0 1 1
0 1 2 0 2 2
0 1 2 0 2 2
0 2 2 2 3 3
3 3 3 0 0 0

Înălțimea maximă este 3 iar aria maximă a unei suprafețe de înălțime 3, este tot 3 (căsuțele îngroșate)

#include <bits/stdc++.h>
using namespace std;
ifstream cin("meteoriti.in");
ofstream cout("meteoriti.out");

int n , m , nr , x1 , x2 , y1 , y2 , add , maxi , cnt;
int a[2002][2002], numar;

struct poz{int i , j;};

bool inside(int i , int j)
{
    return (i>=1 && i<=n && j>=1 && j<=m);
}
int x, y;
inline void Fill()
{
    if (!inside(x, y))return;
    if (a[x][y] != maxi)return;
    a[x][y] = -1;
    numar ++;
    
    x ++;Fill();x --;
    y ++;Fill();y--;
    x --;Fill();x ++;
    y --;Fill();y ++;
}
int main()
{
    cin >> n >> m >> nr;
    for (int i = 1; i <= nr; i ++)
    {
        cin >> x1 >> y1 >> x2 >> y2 >> add;
        a[x1][y1] += add;
        a[x1][y2 + 1] -= add;
        a[x2 + 1][y1] -= add;
        a[x2 + 1][y2 + 1] += add;
    }
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            a[i][j] = a[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];

    int mx = 0;
    for(int i = 1 ; i <= n ; ++i)
    {
        for(int j = 1 ; j <= m ; ++j)
        {
            if(a[i][j] > maxi) maxi = a[i][j];
            if(a[i][j] == 0) cnt++;
        }
    }
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            if(a[i][j] == maxi)
            {
                numar = 0;
                x = i; y = j;
                Fill();
                mx = max(numar, mx);
            }
         cout << mx << " " << cnt;
    return 0;
}