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$ 行目は角 $i$ を空白区切り整数 $T_{i}$、$S_{i}$ で表します。

出力

• $1$ 行目：スタートからゴールまで両端を含めた最高速度の整数。

入出力例

入力 1

14 3
7 3
11 1
13 8

出力 1

5

問題作成者：Brian Jacokes、2009