#3746. 赶牛入圈

    ID: 3746 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>基础语法前缀和与差分算法竞赛进阶指南基本算法0x08二分

赶牛入圈

题目描述

农夫约翰希望为他的奶牛们建立一个畜栏。

这些挑剔的畜生要求畜栏必须是正方形的,而且至少要包含 C 单位的三叶草,来当做它们的下午茶。

畜栏的边缘必须与 X,Y 轴平行。

约翰的土地里一共包含 N 单位的三叶草,每单位三叶草位于一个 1×1 的土地区域内,区域位置由其左下角坐标表示,并且区域左下角的 X,Y 坐标都为整数,范围在 1 到 10000 以内。

多个单位的三叶草可能会位于同一个 1×1 的区域内,因为这个原因,在接下来的输入中,同一个区域坐标可能出现多次。

只有一个区域完全位于修好的畜栏之中,才认为这个区域内的三叶草在畜栏之中。

请你帮约翰计算一下,能包含至少 C 单位面积三叶草的情况下,畜栏的最小边长是多少。

输入格式

第一行输入两个整数 C 和 N。

接下来 N 行,每行输入两个整数 X 和 Y,代表三叶草所在的区域的 X,Y 坐标。

同一行数据用空格隔开。

输出格式

输出一个整数,代表畜栏的最小边长。

数据范围

  • 1C5001≤C≤500
  • CN500C≤N≤500

样例

3 4
1 2
2 1
4 1
5 2
4

来源

  • USACO 2006 Jan.
  • poj3179
  • 算法竞赛进阶指南