logo AlgoBeat OnlineJudge
登录 注册

#101810. [BZOJ 1810] [Ioi2005]gar

内存限制:64 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

Byteman 拥有镇上最漂亮的花园。他在自己的花园里面种了 朵玫瑰花。夏天来了,所有的花都开的非常的漂亮。Byteman 开始意识到自己没有能力看管自己花园里的所有的花,所以他决定雇佣两个园丁来帮助他。他想在花园中选择两块矩形的区域分别交给两个园丁看管。而且这两个矩形区域必须不能相交或者重叠,并且每一个区域要恰好包含K朵玫瑰花。

Byteman 想要给这两块矩形区域的周围安上栅栏,但是他现在手头比较紧,所以他希望自己花的钱尽量的少。你的任务就是帮助 Byteman 选择两块矩形的区域,使得它们在满足条件的情况下周长和最小。 Byteman 的花园有 米长, 米宽。花园被分成了 个大小相同的方格。我们以平行与花园的两边建立起一个坐标系。所有的方格的坐标 满足 1\leq L1\leq L2\leq L1\leq W1\leq W2\leq W(L1,W1)(L1,W2)(L2,W1)(L2,W2)$:

  • 这个矩形内所包含的点的坐标 满足 并且 .
  • 这个矩形的周长是 . 所选的两块矩形不能重叠或者相交。也就是它们不能有公共的方格。即使它们有公共的边,计算周长的时候也要分别计算。

输入格式

第一行是 ; 第二行是 ; 接下来 行为 朵玫瑰的坐标;

输出格式

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

样例

样例输入 #1

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

样例输出 #1

22

数据范围与提示

对于50%的数据:.

对于100%的数据:

没有写明提示 没有写明来源