题目描述

贝茜从山顶滑雪到山脚，山顶到山脚距离是$\red{L( 2≤}$$\red{L≤}$$\red{10^9)}$米.贝茜在起点的速度是$\red{1}$米每秒，但是他的速度是可以改变的，在每一米的速度可 以是前一米的速度加$\red{1}$、减$\red{1，}$或者等于前一米的速度.

在滑行的过程中，贝茜会遇到$\red{N(1<N≤}$$\red{100000)}$个转弯处，第i个转弯处位于距离出发点$\red{T_i(1<T_i<L-1)}$米处,为了安全，贝茜到达第i个转弯处的速度不能超过$\red{S_i(1<S_i≤}$$\red{10)}$米每秒，当然贝茜到达终点时的速度没有最大限制.

请你计算贝茜在滑雪过程中最大的速度可以是多少?

看下面的例子，有距离开始$\red{7}$米$\red{(}$最大限速为$\red{3)}$、$\red{11}$米$\red{(}$最大限速为$\red{1)}$、$\red{13}$米$\red{(}$最大限速为$\red{8)}$处有转弯.

请看下面的图表，分别描述了每一米的速度:限速距离速度

通过上面的图可以看出，距离出发点$\red{1}$米处的速度是$\red{2，}$距离出发点$\red{2}$米处的速度是$\red{3，}$距离出发点$\red{3}$米处的速度是$\red{4，}$距离出发 点$\red{4}$米处的速度是$\red{5，}$距离出发点$\red{5}$米处的速度是$\red{5}$......

输入格式

第$\red{1}$行：两个正整数$\red{L, N.}$

第$\red{2}$到$\red{N+1}$行：第$\red{i+l}$行描述第$\red{i}$个转弯处的两个参数$\red{T_i，}$$\red{S_i}$．

输出格式

一个整数，表示在滑雪中能取得的最大速度（包括起点和终点的速度）

样例

输入样例

14 3
7 3
11 1
13 8

输出样例

5