|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||8||7||7||87.500%|
You, a proud pipe fitter of ICPC (International Community for Pipe Connection), undertake a new task. The area in which you will take charge of piping work is a rectangular shape with W blocks from west to east and H blocks from north to south. We refer to the block at the i-th from west and the j-th from north as (i, j). The westernmost and northernmost block is (1, 1), and the easternmost and southernmost block is (W, H). To make the area good scenery, the block (i, j) has exactly one house if and only if both of i and j are odd numbers.
Your task is to construct a water pipe network in the area such that every house in the area is supplied water through the network. A water pipe network consists of pipelines. A pipeline is made by connecting one or more pipes, and a pipeline with l pipes is constructed as follows:
In addition, you should notice the followings when you construct several pipelines:
In your task, common pipes are common, so you can use any number of common pipes. On the other hand, special pipes are special, so the number of available special pipes in this task is restricted under ICPC regulation.
Besides the restriction of available special pipes, there is another factor obstructing your pipe work: fierce dogs. Some of the blocks which do not contain a house seem to be home of fierce dogs. Each dog always stays at his/her home block. Since several dogs must not live at the same block as their home, you can assume each block is home of only one dog, or not home of any dogs.
The figure below is an example of a water pipe network in a 5 × 5 area with 4 special pipes. This corresponds to the first sample.
Locating a common pipe at a no-dog block costs 1 unit time, but locating a common pipe at a dog-living block costs 2 unit time because you have to fight against the fierce dog. Note that when you locate multiple pipes at the same block, each pipe-locating costs 1 unit time for no-dog blocks and 2 for dog-living blocks, respectively. By the way, special pipes are very special, so locating a special pipe costs 0 unit time.
You, a proud pipe fitter, want to accomplish this task as soon as possible. Fortunately, you get a list of blocks which are home of dogs. You have frequently participated in programming contests before being a pipe fitter. Hence, you decide to make a program determining whether or not you can construct a water pipe network such that every house is supplied water through the network with a restricted number of special pipes, and if so, computing the minimum total time cost to construct it.
The input consists of a single test case.
W H K N x1 y1 ... xN yN
All numbers in a test case are integers. The first line contains three integers W, H, and K. W and H represent the size of the rectangle area. W is the number of blocks from west to east (1 ≤ W < 10,000), and H is the number of blocks from north to south (1 ≤ H < 10,000). W and H must be odd numbers. K is the number of special pipes that you can use in this task (1 ≤ K ≤ 100,000,000). The second line has an integer N (0 ≤ N ≤ 100,000), which is the number of dogs in the area. Each of the following N lines contains two integers xi and yi, which indicates home of the i-th fierce dog is the block (xi, yi). These numbers satisfy the following conditions:
If we can construct a water pipe network such that every house is supplied water through the network with a restricted number of special pipes, print the minimum total time cost to construct it. If not, print -1.
5 5 4 6 3 2 4 2 5 2 1 4 3 4 5 4
5 3 1 0
9 5 100 5 2 1 1 2 3 4 4 3 2 2
5 5 3 4 1 2 5 2 1 4 5 4
9 5 5 10 2 1 2 2 3 2 5 2 8 2 4 3 2 4 3 4 5 4 8 4