AT_abc415_g [ABC415G] Get Many Cola

> 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.

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 the answer as an integer.

### Sample Explanation 1 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 Explanation 2 He can only drink the bottled colas he originally had. ### 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.