/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 575 点
問題文
本問題の設定は D 問題と類似しています。D 問題とは、最大化の対象および制約の一部が異なります。
不思議なコーラショップがあります。 このショップは直接コーラを売ることはしませんが、コーラの空き瓶と新しい瓶入りコーラとの交換サービスを提供しています。
はじめ、高橋君は瓶入りコーラを N 本持っており、これから以下のいずれかの行動を選んで取ることを好きな回数繰り返すことができます（0 回でもよい）。
- 持っている瓶入りコーラ 1 本を飲む。持っている瓶入りコーラの本数が 1 減り、空き瓶の本数が 1 増える。 （行動前に 1 本も瓶入りコーラを持っていない場合、この行動は取れない。）
- 1 以上 M 以下の整数 i を選ぶ。コーラショップに A_i 本の空き瓶を渡し、引き換えに B_i 本の瓶入りコーラをもらう。 （行動前に持っている空き瓶の本数が A_i 未満であるような i は選ぶことができない。 選ぶことのできる i が存在しない場合、この行動は取れない。）
高橋君はコーラが大好きです。うまく行動を取ったとき、最大で何本のコーラを飲むことができますか？
なお、高橋君は最初空き瓶を 1 本も持っていないものとします。
制約
- 1\leq N \leq 10^{15}
- 1\leq M \leq 2\times 10^5
- 1\leq B_i < A_i \leq 300
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
出力
答えを整数として出力せよ。
入力例 1
5 3 5 4 5 1 4 2
出力例 1
11
以下のような行動を考えます。
- 最初、高橋君は瓶入りコーラを 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 です。
入力例 2
3 3 5 1 4 2 5 1
出力例 2
3
元々持っている瓶入りコーラを飲むことしかできません。
入力例 3
925532735634776 8 91 40 273 265 286 153 155 126 92 83 291 228 216 90 234 9
出力例 3
31583804603529464
Score : 575 points
Problem Statement
The setting of this problem is similar to Problem D. It differs from Problem D in the target of maximization and some constraints.
There is a mysterious cola shop. This shop does not sell cola directly, but provides an exchange service between empty cola bottles and new bottled cola.
Initially, Takahashi has N bottled colas, and from now on he can choose and take one of the following actions any number of times (possibly zero):
- Drink 1 bottled cola that he has. The number of bottled colas he has decreases by 1, and the number of empty bottles increases by 1. (If he has no bottled cola before the action, he cannot take this action.)
- Choose an integer i between 1 and M, inclusive. Give A_i empty bottles to the cola shop, and receive B_i bottled colas in return. (He cannot choose i such that the number of empty bottles he has before the action is less than A_i. If there is no i that can be chosen, he cannot take this action.)
Takahashi loves cola. When he acts optimally, what is the maximum number of colas he can drink?
He initially has no empty bottles.
Constraints
- 1\leq N \leq 10^{15}
- 1\leq M \leq 2\times 10^5
- 1\leq B_i < A_i \leq 300
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
Output
Output the answer as an integer.
Sample Input 1
5 3 5 4 5 1 4 2
Sample Output 1
11
Consider the following actions:
- Initially, Takahashi has 5 bottled colas.
- Repeat drinking 1 bottled cola 5 times. Takahashi has 5 empty bottles.
- Make an exchange with i=1, giving 5 empty bottles in exchange for 4 bottled colas. Takahashi has 4 bottled colas.
- Repeat drinking 1 bottled cola 4 times. Takahashi has 4 empty bottles.
- Make an exchange with i=3, giving 4 empty bottles in exchange for 2 bottled colas. Takahashi has 2 bottled colas.
- Repeat drinking 1 bottled cola 2 times. Takahashi has 2 empty bottles.
At this point, Takahashi has drunk a total of 5+4+2=11 colas. No matter how he acts, he cannot drink 12 or more colas, so the answer is 11.
Sample Input 2
3 3 5 1 4 2 5 1
Sample Output 2
3
He can only drink the bottled colas he originally had.
Sample Input 3
925532735634776 8 91 40 273 265 286 153 155 126 92 83 291 228 216 90 234 9
Sample Output 3
31583804603529464