Evacuation#4370

Evacuation

2 seconds

128 megabytes

Medium

Dramatic events are unfolding: an old spider was resting on its rectangular web when suddenly, parts of it caught fire. Fortunately, the spider had prepared a special cell for evacuation. Now, it must reach this cell by taking the safest path possible.

The web is a rectangular grid ranging from $(1, 1)$ to $(a, b)$ . The locations where the fire starts are known. The spider begins at $(1, 1)$ and needs to reach the evacuation point at $(a, b)$ . The spider moves along the grid edges, taking $1$ second per move, while the fire spreads every $t$ seconds. The spider cannot occupy a vertex that is on fire.

Let's define the concept of path danger. For any given path, a vertex is considered dangerous if, at the time the spider passes through it, at least one adjacent vertex is on fire. The danger of a path is the total number of dangerous vertices along it. The spider aims to minimize this danger for its safety. Can you help it find the safest path?

Input

The first line contains the integers $a$ and $b$ ( $1 \leq a, b \leq 500$ 1 \leq a, b \leq 500) representing the dimensions of the web. The second line contains the integer $t$ ( $1 \leq t \leq 100$ 1 \leq t \leq 100), which is the time interval for the fire to spread. The third line contains the integer $k$ ( $1 \leq k \leq a \cdot b$ 1 \leq k \leq a \cdot b), representing the number of ignition points. The following $k$ lines each contain two integers, indicating the coordinates of the vertices that are on fire.

Output

Output the minimum danger level of the path from $(1, 1)$ to $(a, b)$ . If no such path exists, output "-1".

Examples

Example

Example

-1

Example 1

Note

In the first example, the spider follows the path $(1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (3, 3) \to (4, 3)$ (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (4, 3). Initially, $(1, 1)$ is dangerous because the adjacent cell $(2, 1)$ is on fire. At $(1, 2)$ , only $(2, 1)$ is burning, so $(1, 2)$ is safe. When the spider reaches $(1, 3)$ , additional cells catch fire, but none are adjacent to $(1, 3)$ , making it safe. At $(2, 3)$ , the adjacent cell $(2, 2)$ is on fire, making $(2, 3)$ dangerous. At $(3, 3)$ , more cells catch fire, including $(3, 2)$ , making $(3, 3)$ dangerous. Finally, at $(4, 3)$ , no new cells catch fire, and none of the burning ones are adjacent, so it is safe. The path danger is $3$ , with dangerous vertices at $(1, 1)$ , $(2, 3)$ , and $(3, 3)$ . No other path avoids burning cells.

In the second example, after three seconds, $(4, 3)$ catches fire, preventing the spider from reaching it in time.