Pole uprawne

Limit pamięci: 128 MB

Tym razem Bajtocja ma kształt prostokąta o wymiarach na metrów. Bajtazar jest farmerem i ma swoje pole uprawne, składające się z obszarów jednostkowych. Ponadto część wspólna każdej poziomej warstwy obszarów jednostkowych z polem Bajtazara jest spójna (samo pole jednakże nie musi być spójne).

Król Bajtocji wydał dekret, na mocy którego z każdego pola uprawnego należy oddać królowi prostokątny obszar o wymiarach na metrów, złożony wyłącznie z całych obszarów jednostkowych. Jego położenie wybiera sam król. Jedyną nadzieją farmera Bajtazara jest to, że istnieje bardzo dużo możliwych takich położeń i być może zachłannemu królowi nie uda się zbyt szybko podjąć decyzji o wyborze położenia. Pomóż Bajtazarowi i policz, ile jest możliwych położeń takiego obszaru na polu Bajtazara?

Zadanie

• wczyta ze standardowego wejścia opis pola uprawnego farmera i rozmiary prostokątnego obszaru, który ma być oddany królowi,
• obliczy liczbę możliwych położeń takiego obszaru na polu,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się cztery liczby całkowite , , i (), oznaczające odpowiednio wymiary Bajtocji oraz wymiary prostokątnego obszaru, który ma być oddany królowi. Kolejnych wierszy zawiera opisy kolejnych poziomych warstw pola Bajtazara. Każdy z nich składa się z dwóch liczb całkowitych i (, , ) oznaczających, że fragment pola na tej warstwie zaczyna się metrów od lewego brzegu Bajtocji i składa się z obszarów jednostkowych.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, oznaczającą liczbę możliwych położeń prostokąta o wymiarach na na polu Bajtazara.

Przykład

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

3

Powyższy rysunek przedstawia pole uprawne z przykładowego wejścia (powierzchnia należąca do pola została zamalowana na czarno).

Uwaga

Programujących w C++ zachęcamy do rozważnego korzystania z STL-owych struktur danych, ponieważ ze względu na rozmiar danych, ich używanie może spowodować przekroczenie limitu czasowego lub pamięciowego.

Autor zadania: Jakub Radoszewski.