P0486

[Ioi2005]gar

[Ioi2005]gar

Byteman 拥有镇上最漂亮的花园。他在自己的花园里面种了 NN 朵玫瑰花。夏天来了，所有的花都开得非常漂亮。Byteman 开始意识到自己没有能力看管花园里的所有的花，所以他决定雇佣两个园丁来帮助他。

他想在花园中选择两块矩形的区域分别交给两个园丁看管，而且这两个矩形区域必须不能相交或者重叠，并且每一个区域要恰好包含 KK 朵玫瑰花。

Byteman 想要给这两块矩形区域的周围安上栅栏，但是他现在手头比较紧，所以他希望自己花的钱尽量少。你的任务就是帮助 Byteman 选择两块矩形的区域，使得它们在满足条件的情况下周长和最小。

Byteman 的花园有 LL 米长，WW 米宽。花园被分成了 L×WL\times W 个大小相同（1×11\times 1）的方格。我们以平行于花园的两边建立起一个坐标系，所有方格的坐标 (x,y)(x, y) 满足 1≤x≤L1\le x\le L，1≤y≤W1\le y\le W。每个方格内可能会有任意数目的玫瑰。

所选的矩形区域的两边必须跟花园的两边平行，并且矩形区域的四个角的坐标必须是整数。对于 1≤L1≤L2≤L1\le L_1\le L_2\le L 并且 1≤W1≤W2≤W1\le W_1\le W_2\le W，一个四个角为 (L1,W1),(L1,W2),(L2,W1),(L2,W2)(L_1, W_1), (L_1, W_2), (L_2, W_1), (L_2, W_2) 的矩形区域满足：

  • 这个矩形内所包含的点的坐标 (x,y)(x, y) 满足 L1≤x≤L2L_1\le x\le L_2 并且 W1≤y≤W2W_1\le y\le W_2；
  • 这个矩形的周长是 2(L2−L1+1)+2(W2−W1+1)2(L_2-L_1+1)+2(W_2-W_1+1)。

所选的两块矩形不能重叠或者相交，也就是它们不能有公共的方格。即使它们有公共的边，计算周长的时候也要分别计算。

输入格式

第一行是两个整数 LL 和 WW。

第二行是两个整数 NN 和 KK。

接下来 NN 行为 NN 朵玫瑰的坐标。

输出格式

输出仅有一行，为最小周长。如果不存在满足题意的矩形，则输出 NO。

样例输入

6 5
7 3
3 4
3 3
6 1
1 1
5 5
5 5
3 1

样例输出

22

数据范围

  • 1≤L,W≤2501\le L, W\le 250；
  • 2≤N≤50002\le N\le 5000，1≤K≤N/21\le K\le N/2；
  • 50%50\% 的数据中，W≤40W\le 40。

来源与许可

本题为 IOI 2005 试题「gar」，题面与测试数据整理自 BZOJ 1810。

样例 1

输入

6 5
7 3
3 4
3 3
6 1
1 1
5 5
5 5
3 1

输出

22