Description

【题意】
贝西参加了一场高山急速滑雪比赛，滑道总长度为 $L$。
出发时，她的初速度为 $1$，贝西可以加速或减速，每过 $1$ 米，她能将速度增加 $1$、减少 $1$或保持不变。
在滑雪的过程中，贝西会遇到 $N$ 个转弯点，编号为 $i$的转弯点距离起点有 $T_i$米。
安全起见，贝西到达 $i$ 号转弯点时的速度不能超过 $S_i$。
穿过终点的速度是没有限制的。请问在整个比赛过程中，贝西能够达到的最大速度是多少？

【输入格式】
第一行：两个整数 $L$ 和 $N$，$2 \le L \le 10^9,1 \le N \le 10^5$
第二行到第 $N+1$ 行：第 $i+1$ 行有两个整数 $T_i$ 和 $S_i$，$1 \le T_i < L,1 \le S_i \le 10^9$

【输出格式】
单个整数：表示贝西在比赛过程中能够达到的最大速度

【样例输入】
14 3
7 3
11 1
13 8

【样例输出】
5

【解释】

第一次达到最高速度的位置在距离起点4米处

Hint

本题不保证转弯点按从起点由近到远的顺序排列。