Problem 26048 --围栏问题

26048: 围栏问题

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 8  Solved: 2
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][180kb]

Description

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

Input

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

Output

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

Sample Input

6 1 4 
1 3 
4 2 
4 4
6 4

Sample Output

18

HINT


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






【输入输出样例解释2】

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














Source

[Submit][Status]