问题 26048 --围栏问题

26048: 围栏问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 8  解决: 2
[提交][状态][讨论版][命题人:]

题目描述

在一片草原上,有n只兔子无忧无虑地生活着。这片草原可以划分成m×m的方阵。每个方格内最多有一只兔子。
一位饲养员负责喂养这些兔子。为了方便,她需要用篱笆建造最多k座围栏,将草原上的兔子全部围起来。
围栏需要满足以下条件: 
(1)必须沿着网格线建造; 
(2)每座围栏是一个不与自身重叠或相交的封闭回路; 
(3)各座围栏之间互相不重叠、不相交; 
(4)一座围栏不能被围在另一座围栏里面。
请你帮助饲养员计算一下围栏总长度的最小值。

输入

输入文件名为fence.in 
输入第1行为三个整数m,k,n。
接下来n行每行为一对正整数x,y,表示第x行第y列的方格中有一只兔子。

输出

输出文件名为fence.out 
输出仅1行,为一个正整数,表示围栏总长度的最小值。

样例输入

6 1 4 
1 3 
4 2 
4 4
6 4

样例输出

18

提示


如图是一种满足题意的建造方法。






【输入输出样例解释2】

如图是一种满足题意的建造方法。














来源

 

[提交][状态]