[IOI2005] gar
题目背景
Byteman 拥有镇上最漂亮的花园。
题目描述
他在自己的花园里面种了 $N$ 朵玫瑰花。
夏天来了,所有的花都开的非常的漂亮。 Byteman 开始意识到自己没有能力看管自己花园里的所有的花,所以他决定雇佣两个园丁来帮助他。
他想在花园中选择两块矩形的区域分别交给两个园丁看管。而且这两个矩形区域必须不能相交或者重叠,并且每一个区域要恰好包含 $K$ 朵玫瑰花。
Byteman 想要给这两块矩形区域的周围安上栅栏,但是他现在手头比较紧,所以他希望自己花的钱尽量的少。你的任务就是帮助 Byteman 选择两块矩形的区域,使得它们在满足条件的情况下周长和最小。
Byteman 的花园有 $L$ 米长,$W$ 米宽。花园被分成了 $L\times W$ 个大小相同 $1\times1$ 的方格。我们以平行与花园的两边建立起一个坐标系。所有的方格的坐标 $(x,y)$ 满足 $1\leq x\leq L,1\leq y\leq W$。每个方格内可能会有任意数目的玫瑰。
所选的矩形区域的两边必须跟花园的两边平行,并且矩形区域的四个角的坐标必须是整数。对于 $1\le L_1\le L_2\le L$ 并且 $1\le W_1\le W_2\le W$,一个矩形区域的四个角为 $(L_1,W_1),(L_1,W_2)$,$(L_2,W_1)$ 和 $(L_2,W_2)$:
* 这个矩形内所包含的点的坐标 $(x,y)$ 满足$L_1\le x\le L_2$并且$W_1\le y\le W_2$。
* 这个矩形的周长是 $2\times (L_2-L_1+1)+2\times (W_2-W_1+1)$。所选的两块矩形不能重叠或者相交。也就是它们不能有公共的方格。即使它们有公共的边,计算周长的时候也要分别计算。
输入输出格式
输入格式
第一行是 $L$ 和 $W$。
第二行是 $N$ 和 $K$。
接下来 $N$ 行为 $N$ 朵玫瑰的坐标。
输出格式
输出仅有一行,为最小周长。
如果不存在满足题意的矩形,则输出`NO`。
输入输出样例
输入样例 #1
6 5
7 3
3 4
3 3
6 1
1 1
5 5
5 5
3 1
输出样例 #1
22
说明
对于$100\%$的数据,$1\le L,W\le250$,$2\le n\le5000,1\le k\le \frac{n}{2}$