Enunț

Păcală a reușit să ducă la bun sfârșit înțelegerea cu boierul căruia-i fusese slugă și, conform învoielii, boierul trebuie să-l răsplătească dându-i o parte din livada sa cu pomi fructiferi. Boierul este un om foarte ordonat, așa că livada sa este un pătrat cu latura de N metri unde, pe vremuri, fuseseră plantate N rânduri cu câte N pomi fiecare. Orice pom fructifer putea fi identificat cunoscând numărul rândului pe care se află și poziția sa în cadrul rândului respectiv. Cu timpul, unii pomi s-au uscat şi acum mai sunt doar P pomi. Păcală trebuie să-și delimiteze în livadă o grădină pătrată cu latura de K metri.

Cerința

Cunoscând dimensiunile livezii și grădinii, numărul pomilor din livadă și poziția fiecăruia, determinați numărul maxim de pomi dintr-o grădină pătrată de latură K și numărul modurilor în care poate fi amplasată grădina cu numărul maxim de pomi.

Date de intrare

Fișierul gradina.in conține:

• pe prima linie numerele naturale N, P și K, separate prin câte un spațiu, cu semnificaţia din enunţ;
• pe următoarele P linii câte 2 numere naturale Lin și Col, separate printr-un spațiu, reprezentând numărul rândului, respectiv poziția în rând a fiecărui pom din livadă.

Date de ieșire

Fișierul gradina.out va conține:

• pe prima linie numărul maxim de pomi fructiferi dintr-o grădină pătrată cu latura de K metri;
• pe a doua linie numărul de posibilități de a amplasa grădina astfel încât să conțină numărul maxim de pomi determinat.

Restricții și precizări

• 2 ≤ N ≤ 1000
• 1 ≤ P ≤ N*N
• 1 ≤ K ≤ N

Exemplu

gradina.in

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

gradina.out

5
5

Explicație

Grădina lui Păcală poate avea maximum 5 pomi fructiferi. Ea poate fi amplasată în 5 moduri, având colțul stânga-sus de coordonate: (5, 3), (5, 4), (5, 5), (6, 6), (7, 3).

#include <bits/stdc++.h>
using namespace std;
ifstream cin("gradina.in");
ofstream cout("gradina.out");
int n , p , k , a[1001][1001] ,d[1001][1001] , x , y , cnt , maxi , s;
int main()
{
    cin >> n >> p >> k;
    for(int i = 0 ; i < p ; ++i)
        cin >> x >> y , a[x][y]=1;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+a[i][j];
    for(int i = k ; i <= n ; ++i)
        for(int j = k ; j <= n ; ++j)
        {
            s=d[i][j]-d[i-k][j]-d[i][j-k]+d[i-k][j-k];
            if(s > maxi) maxi=s , cnt=0;
            if(s == maxi) cnt++;
        }
    cout << maxi << endl << cnt;
    return 0;
}