### 2016 Canadian Computing Olympiad

## Day 2, Problem 2 - Zombie Apocalypse

Your country has a problem with zombies. That is, it has zombies, which are a problem. Thankfully, you are gainfully employed at the Forsenic 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 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 Format

The first line of input will contain two space-separated integers `N` and `M` (1 ≤ `N` ≤ 10^{9}; 1 ≤ `M` ≤ 10^{9}) indicating the size of the grid. The next line contains the number `K` (1 ≤ `K` ≤ 2000), indicating the number of cells that contain zombies. The next `K` lines each contain two space-separated integers `r _{i}`

`c`indicating the row and column of the

_{i}`i`-th zombie (1 ≤

`r`≤

_{i}`N`; 1 ≤

`c`≤

_{i}`M`). No two zombies are in the same cell: thus if

`i`≠

`j`then (

`r`,

_{i}`c`) ≠ (

_{i}`r`,

_{j}`c`). The last line will contain the integer

_{j}`Q`(0 ≤

`Q`≤

`N`+

`M`).

For 5 of the 25 marks available, `N` ≤ 1000 and `M` ≤ 1000.

For an additional 5 of the 25 marks available, `K` ≤ 50.

For an additional 5 of the 25 marks available, `N` ≤ 1000.

### Output Format

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.

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 64M

**Added:** May 14, 2016

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...