問題文

やきとりくんは、これから $N$ 日間の間に課される $M$ 個の宿題を行おうとしています。
$i \: (1 \leq i \leq M)$ 個目の宿題は、$L_i$ 日目以降に行うことができ、宿題を終わらせるのには $C_i$ 日の作業が必要です。
また、やきとりくんは同時に複数の宿題を行うことはできません。

やきとりくんが宿題を全て終わらせることができるのは最速で何日目でしょうか。

制約

• $1 \leq N \leq 10^9$
• $1 \leq M \leq 10^5$
• $1 \leq L_i \leq N$
• $1 \leq C_i \leq 10^9$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

出力

問題の答えを一行に出力せよ。

入出力例

10 3
1 3
5 2
6 5

11

例えば、以下のように宿題を行うと最速で全ての宿題を終わらせることができます。

• $2$ 日目 から $4$ 日目 に $1$ 個目の宿題を行う。
• $5$ 日目 から $6$ 日目 に $2$ 個目の宿題を行う。
• $7$ 日目 から $11$ 日目 に $3$ 個目の宿題を行う。

最速で $11$ 日目に全ての宿題を終わらせることができるため、$11$ と出力します。
上の例のように、答えは与えられた $N$ よりも大きくなることがあることに注意してください。

755714 6
4868 46885
20375 55186
28700 54565
49781 32105
65836 59923
1390 8116

258169