Cerința

Maria dansează! Lecțiile de dans se desfășoară într-o sală imensă, împărțită în n*m sectoare pătratice cu dimensiunea 1, dispuse pe n linii și m coloane. În anumite sectoare se află diverse obstacole, astfel că acele sectoare nu pot fi utilizate pentru dans. Maria are nevoie pentru dans de o zonă dreptunghiulară de dimensiuni p, q, cu laturile paralele cu pereții sălii, care să nu conțină obstacole și vrea ca în fiecare zi să danseze într-o zonă diferită de cele în care a dansat deja. Determinați numărul de zile în care Maria poate dansa așa cum își dorește.

Date de intrare

Fișierul de intrare maria.in conține pe prima linie numerele n m p q. A doua linie conține numărul k de sectoare din sală în care se află obstacole. Fiecare dintre următoarele k linii conține două numere i j, reprezentând linia și coloana unui sector ce conține un obstacol.

Date de ieșire

Fișierul de ieșire maria.out va conține pe prima linie numărul Z de zile în care Maria poate dansa în zone diferite.

Restricții și precizări

• 1 ≤ n, m , p , q ≤ 1000
• 0 ≤ k ≤ 1000
• 1 ≤ i ≤ n, 1 ≤ j ≤ m
• două zone de dans sunt distincte dacă diferă prin cel puțin un sector
• zona de dans poate fi orientată astfel încât să ocupe p linii și q coloane sau q linii și p coloane

Exemplu

maria.in

5 6 2 3
3
2 2
3 5
4 3

maria.out

5

Explicație

Cele 5 moduri de stabilire a zonei de dans sunt:

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

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

int n , m , p , q , a[1001][1001] , k , x , y , s[1001][1001] , cnt;

bool inside(int i , int j)
{
    return i >= 1 && i <= n && j >= 1 && j <= m;
}

int main()
{
    cin >> n >> m >> p >> q >> k;
    for(int i = 1 ; i <= k ; i++)
    {
        cin >> x >> y;
        a[x][y] = 1;
    }

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];

    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= m ; j++)
        {
            int inou = i + p - 1 , jnou = j + q - 1;
            if(inside(inou , jnou) && s[inou][jnou] - s[i - 1][jnou] - s[inou][j - 1] + s[i - 1][j - 1] == 0) cnt++;
            inou = i + q - 1 , jnou = j + p - 1;
            if(inside(inou , jnou) && s[inou][jnou] - s[i - 1][jnou] - s[inou][j - 1] + s[i - 1][j - 1] == 0) cnt++;
        }
    }
    cout << cnt;
}