问题陈述
你,一名ICPC(国际管道连接协会)引以为傲的管道安装工,承担着新的任务。 您负责管道工程的区域是一个矩形,从西到东有 $W$ 块,从北到南有 $H$ 块。 我们将西起第 $i$ 和北起第 $j$ 的区块称为 $(i, j)$。 最西和最北的块是$(1,1)$,最东和最南的块是$(W,H)$。 为了使该区域成为良好的风景,当且仅当$i$和$j$都是奇数时,块$(i,j)$只有一所房子。
你的任务是在该地区建设一个供水管网,使该地区的每户家庭都通过网络供水。 供水管网由管道组成。 管道是由一个或多个管道连接而成,具有$l$管道的管道构造如下:
- 选择第一个房子,并用一个管道将房子连接到地下水源 特种管材.
- 选择第 $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