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.