URI Online Judge | 2113

Sverdlovsk's Incident

By XVII Maratona de Programação IME-USP, 2013 BR Brazil

Timelimit: 1

During the years of the Soviet Union, the name of the city of Yekaterinburg was Sverdlovsk, in honor of Bolshevik Iakov Sverdlov, son of a Jewish craftsman who was excellent speaker and was a major player next to Lenin in the October Revolution of 1905. He was considered honest, energetic and hardworking and respected by all sections of the party. He died at age 34. The city resumed its original name in 1991 by Boris Yeltsin first president of Russia, born in the city.

On April 2, 1979, when the city was still called Sverdlovsk happened one anthrax leak of one a military factory in the city. This incident is often called "biological Chernobyl", and caused about 100 deaths, though the exact number of victims and contaminated's people is unknown. The Soviet Union denied for years the real causes of the accident and all records of the victims had disappeared, because it could have revealed serious violations of the Biological Weapons Convention.

The Soviet authorities had to resort to highly sophisticated decontamination procedures, especially in rural areas. Each rectangular area of ​​dimensions N by M yards has divided into M × N square sections of one square yards. These sectors are identified by the coordinates of their centers, numbered from east to west and from south to north from (1, 1).

Each sector is considered decontaminated if it is covered by at least K agents health. Each agent was able to cover a circular area. The radius of this area varied depending on the equipment used and the experience of the health agent. Your task is to determine how many of these sectors are considered decontaminated, in other words, covered by at least K agents. Consider that a sector is covered if its center is an area covered by a health agent.

Input

The input consists of several test cases and ends with the end of file (EOF).

The first line of each case contains two integers, N (1 ≤ N≤ 103) and M (1 ≤ M ≤ 105), indicating the size of the rectangular area. The second line contains the number of agents,C, and the K number (1 ≤ KC ≤ 103). The C number following lines have the description of Xc (1 ≤ XcN), Yc (1 ≤ YcM) and Rc (0 ≤ Rc ≤ 108)agents where (Xc,Yc) is the center of the circular area with of radius Rc that an agent covers.The input must be read from standard input.

Output

For each case, print the number of sectors that are covered by at least, K agents health. The output should be written to standard output.

Sample Input Sample Output

10 10

2 1

3 3 2

8 8 2

15 15

6 2

4 4 2

5 5 1

6 6 3

7 7 2

10 10 0

11 10 1

26

20