Canadian Computing Olympiad: 2016 Day 2, Problem 2

Your country has a problem with zombies. That is, it has zombies, which are a problem. Thankfully, you are gainfully employed at the Forensic Institute for Zoology and Zombie Emerging Studies (FIZZES), and your job is simply to give a measure of how bad the problem is.

You have mapped out your country on an ~N~-by-~M~ array of cells marked with non-negative integers.

You have the exact locations of all the zombies, and know that no two zombies are in the same location. The cells containing a zombie are marked with 0. Next, all the unmarked cells touching a cell (where touching a cell means touching on any side or corner of a cell; so each cell touches up to ~8~ other cells) marked with 0 are marked with 1. Then, all the unmarked cells touching a cell marked with 1 are marked with 2. This process continues until all the cells are marked. These numbers indicate the level of concern your office has about the spread of zombies.

A small example is shown below.

2 2 1 1 1 2
2 1 1 0 1 2
2 1 0 1 1 2
2 1 1 1 2 2
2 2 2 2 2 3

Your boss has given you an integer ~Q~, and you must determine the number of cells which are marked with the integer ~Q~.

Input Specification

The first line of input will contain two space-separated integers ~N~ and ~M~ ~(1 \le N \le 10^9; 1 \le M \le 10^9)~ indicating the size of the grid. The next line will contain the number ~K~ ~(1 \le K \le 2000)~, indicating the number of cells that contain zombies. The next ~K~ lines each contain two space separated integers ~r_i~ ~c_i~ indicating the row and column of the ~i~th zombie ~(1 \le r_i \le N; 1 \le c_i \le M)~. No two zombies are in the same cell: thus if ~i \ne j~ then ~(r_i, c_i) \ne (r_j, c_j)~. The last line will contain the integer ~Q~ ~(0 \le Q \le N + M)~.

For ~5~ of the ~25~ marks available, ~N \le 1000~ and ~M \le 1000~.

For an additional ~5~ of the ~25~ marks available, ~K \le 50~.

For an additional ~5~ of the ~25~ marks available, ~N \le 1000~.

Due to the official test data being weak, an additional batch worth 1 mark has been added that was constructed to break solutions that are incorrect but AC on the official test data. Data are provided by XTL.

Output Specification

Output the number of cells in the grid that are marked with the integer ~Q~.

Sample Input

5 6
2
3 3
2 4
2

Sample Output

15

Explanation

The sample input is the example shown above, which has ~15~ 2's.