← 返回题目列表

AtCoder · icpc2016autumn_h

H. 管道工和猛犬

中文机器翻译题面 查看原题

问题陈述

你,一名ICPC(国际管道连接协会)引以为傲的管道安装工,承担着新的任务。 您负责管道工程的区域是一个矩形,从西到东有 $W$ 块,从北到南有 $H$ 块。 我们将西起第 $i$ 和北起第 $j$ 的区块称为 $(i, j)$。 最西和最北的块是$(1,1)$,最东和最南的块是$(W,H)$。 为了使该区域成为良好的风景,当且仅当$i$和$j$都是奇数时,块$(i,j)$只有一所房子。

你的任务是在该地区建设一个供水管网,使该地区的每户家庭都通过网络供水。 供水管网由管道组成。 管道是由一个或多个管道连接而成,具有$l$管道的管道构造如下:

  1. 选择第一个房子,并用一个管道将房子连接到地下水源 特种管材.
  2. 选择第 $i$ 个房子 ($2 \le i \le l$),并使用 a 将第 $i$ 个房子连接到第 $(i-1)$ 个房子 普通管。在这种情况下,有一个条件是选择下一个第$i$个房子,因为该区域是坡地。令 $(x,y)$ 为第 $(i-1)$ 个房子的街区。第 $i$ 个房屋必须位于 $(x-2, y+2)$、$(x, y+2)$ 或 $(x+2, y+2)$。连接两栋房屋的公共管道必须分别位于 $(x-1,y+1)$、$(x,y+1)$ 或 $(x+1,y+1)$ 处。

此外,在构建多条管道时还应注意以下事项:

  • 对于每栋房屋,只有一条管道穿过房屋。
  • 一个方块中可以放置多个管道。

在您的任务中,公共管道是公共的,因此您可以使用任意数量的公共管道。 另一方面,特殊管道具有特殊性,因此根据ICPC的规定,该任务中可用的特殊管道的数量受到限制。

除了可用的特殊管道的限制之外,还有一个因素阻碍了你的管道工作:凶猛的狗。 一些没有房屋的街区似乎是凶狗的家。 每只狗总是呆在他/她的家街区。 由于多只狗不得与它们的家住在同一个街区,因此您可以假设每个街区只有一只狗的家,或者没有任何狗的家。

下图是 $5 \times 5$ 区域内具有 $4$ 专用管道的供水管网示例。 这对应于第一个样本。

在没有狗的街区找到一个公共管道需要花费 1 美元单位时间,但是在有狗居住的街区找到一个公共管道需要花费 2 美元单位时间,因为你必须与凶猛的狗战斗。 请注意,当您在同一街区定位多个管道时,对于无狗街区,每个管道定位成本分别为 1 美元单位时间,对于有狗居住街区,每次管道定位成本分别为 2 美元。 顺便说一句,特殊管道非常特殊,因此定位特殊管道的单位时间成本为 0$。

作为一名自豪的管道安装工,您希望尽快完成这项任务。 幸运的是,您得到了狗的家的街区列表。 在成为管道安装工之前,您经常参加编程比赛。 因此,你决定编写一个程序来确定是否可以建造一个供水管网,使每个房屋都通过有限数量的特殊管道通过网络供水,如果可以,则计算建造它的最小总时间成本。


输入

输入由单个测试用例组成。

$W$$H$$K$
$N$
$x_{1}$ $y_{1}$
...
$x_{N}$ $y_{N}$

测试用例中的所有数字都是整数。 第一行包含三个整数$W$、$H$和$K$。 $W$和$H$表示矩形区域的大小。 $W$ 是从西到东的区块数 ($1 \le W < 10{,}000)$,$H$ 是从北到南的区块数 ($1 \le H < 10{,}000)$。 $W$ 和 $H$ 必须是奇数。 $K$ 是您可以在此任务中使用的特殊管道的数量 ($1 \le K \le 100{,}000{,}000$)。 第二行有一个整数$N$ ($0 \le N \le 100{,}000$),它是该区域中狗的数量。 接下来的$N$行中每一行都包含两个整数$x_i$和$y_i$,这表明第$i$只猛狗的家是块$(x_i, y_i)$。 这些数字满足以下条件:

  • $1 \le x_{i} \le W$,$1 \le y_{i} \le H$。
  • $x_i$ 和 $y_i$ 至少有一个是偶数。
  • $i \neq j$ 意味着 $(x_i, y_i) \neq (x_j, y_j)$。也就是说,两只或两只以上的狗不在同一个街区。

输出

如果我们可以建造一个供水管网,使每个房屋都能通过有限数量的专用管道通过网络供水,请打印建造该管网的最小总时间成本。如果不是,则打印-1。



示例输入 1

5 5 4
6
3 2
4 2
5 2
1 4
3 4
5 4

样本输入 1 的输出

6

示例输入 2

5 3 1
0

样本输入 2 的输出

-1

示例输入 3

9 5 100
5
2 1
1 2
3 4
4 3
2 2

样本输入 3 的输出

0

示例输入 4

5 5 3
4
1 2
5 2
1 4
5 4

样本输入 4 的输出

8

示例输入 5

9 5 5
10
2 1
2 2
3 2
5 2
8 2
4 3
2 4
3 4
5 4
8 4

样本输入 5 的输出

10