AT_abc415_g [ABC415G] Get Many Cola

> 本問題の設定は D 問題と類似しています。D 問題とは、最大化の対象および制約の一部が異なります。 不思議なコーラショップがあります。 このショップは直接コーラを売ることはしませんが、コーラの空き瓶と新しい瓶入りコーラとの交換サービスを提供しています。 はじめ、高橋君は瓶入りコーラを $ N $ 本持っており、これから以下のいずれかの行動を選んで取ることを好きな回数繰り返すことができます（ $ 0 $ 回でもよい）。 - 持っている瓶入りコーラ $ 1 $ 本を飲む。持っている瓶入りコーラの本数が $ 1 $ 減り、空き瓶の本数が $ 1 $ 増える。 （行動前に $ 1 $ 本も瓶入りコーラを持っていない場合、この行動は取れない。） - $ 1 $ 以上 $ M $ 以下の整数 $ i $ を選ぶ。コーラショップに $ A_i $ 本の空き瓶を渡し、引き換えに $ B_i $ 本の瓶入りコーラをもらう。 （行動前に持っている空き瓶の本数が $ A_i $ 未満であるような $ i $ は選ぶことができない。 選ぶことのできる $ i $ が存在しない場合、この行動は取れない。） 高橋君はコーラが大好きです。うまく行動を取ったとき、最大で何本のコーラを飲むことができますか？ なお、高橋君は最初空き瓶を $ 1 $ 本も持っていないものとします。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_M $ $ B_M $

答えを整数として出力せよ。

### Sample Explanation 1 以下のような行動を考えます。 - 最初、高橋君は瓶入りコーラを $ 5 $ 本持っている。 - 持っている瓶入りコーラ $ 1 $ 本を飲むことを $ 5 $ 回繰り返す。高橋君は空き瓶を $ 5 $ 本持った状態になる。 - $ i=1 $ として交換を行い、 $ 5 $ 本の空き瓶と引き換えに $ 4 $ 本の瓶入りコーラをもらう。高橋君は瓶入りコーラを $ 4 $ 本持った状態になる。 - 持っている瓶入りコーラ $ 1 $ 本を飲むことを $ 4 $ 回繰り返す。高橋君は空き瓶を $ 4 $ 本持った状態になる。 - $ i=3 $ として交換を行い、 $ 4 $ 本の空き瓶と引き換えに $ 2 $ 本の瓶入りコーラをもらう。高橋君は瓶入りコーラを $ 2 $ 本持った状態になる。 - 持っている瓶入りコーラ $ 1 $ 本を飲むことを $ 2 $ 回繰り返す。高橋君は空き瓶を $ 2 $ 本持った状態になる。 このとき、高橋君は合計で $ 5+4+2=11 $ 本のコーラを飲むことができます。 高橋君がどのように行動を取っても $ 12 $ 本以上のコーラを飲むことはできないため、答えは $ 11 $ です。 ### Sample Explanation 2 元々持っている瓶入りコーラを飲むことしかできません。 ### Constraints - $ 1\leq N \leq 10^{15} $ - $ 1\leq M \leq 2\times 10^5 $ - $ 1\leq B_i < A_i \leq 300 $ - 入力は全て整数