Pipe Fitter and the Fierce Dogs

You are a proud pipe fitter of ICPC (International Community for Pipe Connection), and you take on a new task. The area you are in charge of is a rectangle with $W$ blocks from west to east and $H$ blocks from north to south. The block that is $i$-th from the west and $j$-th from the north is called $(i, j)$. The westernmost and northernmost block is $(1, 1)$, and the easternmost and southernmost block is $(W, H)$. To keep the scenery pleasant, block $(i, j)$ has exactly one house if and only if both $i$ and $j$ are odd.

Your task is to build a water pipe network so that every house in the area receives water through the network. A network consists of pipelines. A pipeline is made by connecting one or more pipes, and a pipeline with $l$ pipes is built as follows.

1. Choose a first house and connect it to an underground water source with a special pipe.
2. For each $i$ ($2 \le i \le l$), choose an $i$-th house and connect it to the $(i-1)$-th house with a common pipe. Because the area is on a slope, the choice of the next house is restricted. Let $(x, y)$ be the block of the $(i-1)$-th house. The $i$-th house must be at $(x-2, y+2)$, $(x, y+2)$, or $(x+2, y+2)$, and the common pipe connecting the two houses is placed at $(x-1, y+1)$, $(x, y+1)$, or $(x+1, y+1)$, respectively.

When you build several pipelines, the following rules also apply.

• Exactly one pipeline passes through each house.
• Several pipes can be placed on the same block.

Common pipes are common, so you can use any number of them. Special pipes are special, so ICPC regulations limit the number of special pipes you can use in this task.

Besides that limit, fierce dogs get in the way of your work. Some of the blocks that do not contain a house are homes of fierce dogs. Each dog always stays at its home block. Several dogs never share a home, so each block is home to at most one dog.

The figure below shows a water pipe network in a $5 \times 5$ area built with 4 special pipes. It corresponds to the first sample.

Placing a common pipe on a block without a dog takes 1 unit of time. Placing a common pipe on a block where a dog lives takes 2 units of time, because you have to fight the dog. When several pipes are placed on the same block, each placement costs 1 unit on a dog-free block and 2 units on a dog block. Special pipes are very special, so placing a special pipe takes 0 units of time.

You want to finish the task as soon as possible, and you have a list of the blocks where dogs live. Write a program that decides whether a water pipe network supplying every house can be built with the allowed number of special pipes, and if so, computes the minimum total time needed to build it.

The input is a single test case in the following format.

W H K
N
x1 y1
...
xN yN

All numbers are integers. The first line contains $W$, $H$, and $K$. $W$ is the number of blocks from west to east ($1 \le W < 10000$) and $H$ is the number of blocks from north to south ($1 \le H < 10000$). Both $W$ and $H$ are odd. $K$ is the number of special pipes you can use ($1 \le K \le 100000000$). The second line contains $N$ ($0 \le N \le 100000$), the number of dogs in the area. Each of the following $N$ lines contains two integers $x_i$ and $y_i$, meaning that the home of the $i$-th dog is block $(x_i, y_i)$. These values satisfy the following conditions.

• $1 \le x_i \le W$ and $1 \le y_i \le H$.
• At least one of $x_i$ and $y_i$ is even.
• If $i \ne j$, then $(x_i, y_i) \ne (x_j, y_j)$. No two dogs share a block.

If a water pipe network that supplies every house can be built with at most $K$ special pipes, print the minimum total time needed to build it. Otherwise, print -1.