测试数据来自 system/2164

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　贝茜从山顶滑雪到山脚，山顶到山脚的距离是L米，贝茜在起点的速度是 1 米每秒，但他的速度是可以改变的，在每一米的速度可以是前一米的速度加 1、减 1 或者等于前一米的速度，在滑雪的过程中，贝茜会遇到 \(N\) 个转弯处，第 \(i\) 个转弯处位于距离出发点 \(T_i(1 ≤ Ti ≤ L-1)\) 米处，为了安全，贝茜到达地 \(i\) 个转弯处的速度不能超过 \(S_i(1 ≤ Si ≤ 10^9)\) 米每秒。当贝茜到达终点时的速度没有最大限制。请你计算贝茜在滑雪过程中最大的速度可以是多少？

　　看下面的例子，距离开始 7 米（最大限速 3 ）、11 米（最大限速1）、13 米（最大限速为 8）处有转弯。

　　请看下表，分别描述了贝茜每米处的速度：

　　从表上可以看出，距离出发点距离为 1 米处的速度为 2，距离出发点距离为 2 米处的速度为 3，距离出发点距离为 3 米处的速度为 4，距离出发点距离为 4 米处的速度为 5 ……。　　

【输入格式】

　　第 1 行：两个整数L,N。
　　第 2 到 \(N+1\) 行：第 \(i+1\) 行描述第 \(i\) 个转弯处的两个参数 \(T_i，S_i\)。

【输出格式】

　　一个整数，表示贝茜滑雪过程中的最大速度（包括起点和终点的速度）。

【输入输出样例】

　Input

14 3
7 3
11 1
13 8

　Output

5

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤100 000\)，\(L≤10^9\)

【来源】

　　Mr.he