F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 1810. -- [Ioi2005]gar

1810: [Ioi2005]gar

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 179  Solved: 85
[Submit][Status][Discuss]

Description

Byteman拥有镇上最漂亮的花园。他在自己的花园里面种了N朵玫瑰花。夏天来了,所有的花都开的非常的漂亮。Byteman开始意识到自己没有能力看管自己花园里的所有的花,所以他决定雇佣两个园丁来帮助他。他想在花园中选择两块矩形的区域分别交给两个园丁看管。而且这两个矩形区域必须不能相交或者重叠,并且每一个区域要恰好包含K朵玫瑰花。 Byteman想要给这两块矩形区域的周围安上栅栏,但是他现在手头比较紧,所以他希望自己花的钱尽量的少。你的任务就是帮助Byteman选择两块矩形的区域,使得它们在满足条件的情况下周长和最小。 Byteman的花园有L米长,W米宽。花园被分成了L*W个大小相同(1*1)的方格。我们以平行与花园的两边建立起一个坐标系。所有的方格的坐标(x,y)满足1<=x<=L,1<=y<=W.每个方格内可能会有任意数目的玫瑰。 所选的矩形区域的两边必须跟花园的两边平行,并且矩形区域的四个角的坐标必须是整数。对于1<=L1<=L2<=L 并且 1<=W1<=W2<=W,一个矩形区域的四个角为(L1,W1),(L1,W2),(L2,W1)和(L2,W2): * 这个矩形内所包含的点的坐标(x,y)满足L1<=x<=L2并且W1<=y<=W2. * 这个矩形的周长是 2*(L2-11+1)+2*(W2-W1+1). 所选的两块矩形不能重叠或者相交。也就是它们不能有公共的方格。即使它们有公共的边,计算周长的时候也要分别计算。

Input

第一行是L和W。1≤L,W≤250。 第二行是N和K。2≤n≤5000,1≤k≤n/2。 接下来N行为N朵玫瑰的坐标。 50%的数据中,W≤40.

Output

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

Sample Input

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

Sample Output

22

HINT

Source

[Submit][Status][Discuss]

HOME Back