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$）。過終點速度任意。

求不超彎道限速能達到的最高速度。

如下賽道，整數是公尺標記、括號為限速，如 $[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