Bessie 参加雪橇比赛，希望较重体重能在 $L$ 米赛道（$2 \le L \le 1,000,000,000$）占优势。

她从起点以 $1$ 米/秒出发，沿途可改变速度。在每米中间附近，可利用重力增加 $1$ 米/秒，或制动保持不变、降低 $1$ 米/秒。

下坡中必须通过 $N$（$1 \le N \le 100,000$）个弯。弯 $i$ 在起点后 $T_{i}$ 米（$1 \le T_{i} \le L-1$），进入该弯所在的一米时速度须至多 $S_{i}$ 米/秒（$1 \le S_{i} \le 1,000,000,000$）。过终点速度任意。

帮 Bessie 求不超过弯道限速能达到的最高速度。

考虑下图赛道，整数为米标，括号内为弯道限速，例如 $[3]$：

|   1   2   3   4   5   6   7[3]
|---+---+---+---+---+---+---+
|                            \
起点                         + 8    
                               \
                                + 9    
                                 \
                                  + 10       +++ 14 (终点)
                                   \         /
                              11[1] +---+---+
                                        12  13[8]

下表是她在每米开始处的速度：

在第 $4$ 米开始附近最高速 $5$。

输入格式

• 第 $1$ 行：空格分隔整数 $L$、$N$。

• 第 $2..N+1$ 行：第 $i+1$ 行以空格分隔整数 $T_{i}$、$S_{i}$ 描述弯 $i$。

输出格式

• 第 $1$ 行：整数，起点到终点（包括两端）可达到的最高速度。

样例

输入格式 1

14 3
7 3
11 1
13 8

输出格式 1

5

题目作者：Brian Jacokes，2009