2526. __围栏问题

在一片草原上,有n只兔子无忧无虑地生活着。这片草原可以划分成m×m的方阵。每个方格内最多有一只兔子。一位饲养员负责喂养这些兔子。为了方便,她需要用篱笆建造最多k座围栏,将草原上的兔子全部围起来。

围栏需要满足以下条件:

(1)必须沿着网格线建造;

(2)每座围栏是一个不与自身重叠或相交的封闭回路;

(3)各座围栏之间互相不重叠、不相交;

(4)一座围栏不能被围在另一座围栏里面。

请你帮助饲养员计算一下围栏总长度的最小值。

输入文件名为xfence.in

输入第1行为三个整数m,k,n。

接下来n行每行为一对正整数x,y,表示第x行第y列的方格中有一只兔子。

输出文件名为xfence.out

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

xfence.in

6 1 4

1 3

4 2

4 4

6 4

xfence.out

18

xfence.in

6 2 4

1 3

4 2

4 4

6 4

xfence.out

16

对于10%的数据,k=1;

对于10%~30%的数据,k=2;

对于30%~60%的数据,n≤10;

对于100%的数据,1≤k≤n≤16,m≤1,000。