Time

11:45:01
11 Feb 2012
ACM-ICPC Thailand Southern Region Programming Contest 2011
Left: 3 hours 16 minutes
End: 11.02.2012 15:00
Leader: Informatimukas
Five for week 22
Left: 10 hours 15 minutes
End: 11.02.2012 22:00
Leader: NuM
Version for print

House

   The new Russian man Vitek moved into the private property the land in Mezhdolina of size m squares from north to south and n squares from west to east. On this land he decided to build a house with size a squares from north to south and b squares from west to east. Some squares are redioactive, and Viktor does not want to biuld the house on them. In addition, Vitek wants the distance from the walls of the house to the boundaries of the land be expressed with an integer number of squares. For a long time he was choosing a place for the house, but did not choose - too many possibilities exist. But how many? He begin to count - but couldn't because he was bad at math. Help him.


Specifications

   Input

    The values of m, n, a, b, k, where m, n – the sizes of the land, a, b – the sizes of the house, k – the number of radioactive squares, and then k nonrepeating pairs of integers i, j, which define the coordinates of radioactive squares. It is known that 1a m 5000, 1b n 5000, 0k m*n, 1i m, 1j n

   Output

   Print the number of possibilities to build the house.


Problem information

Time Limit: 3 seconds
Memory Limit: 128 MB
Balls for the passed test: 3.84615
Complexity: 21% 38/48
Autor: Непомнящий Григорий
Source: Турнир Чемпионов, Винница 2010
Classes: Dynamic programming

Example

Example input

5 7 2 4 3 2 5 3 3 3 6

Example output

5


← Оранжерея Problems Велосипед →