AT_abc415_d [ABC415D] Get Many Stickers

> The setting of this problem is similar to Problem G. It differs from Problem G 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 and $ 1 $ commemorative sticker 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 stickers. When he acts optimally, what is the maximum number of stickers he can obtain? He initially has no empty bottles and no stickers.

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=2 $ , giving $ 4 $ empty bottles in exchange for $ 3 $ bottled colas and $ 1 $ sticker. Takahashi has $ 3 $ bottled colas, $ 1 $ empty bottle, and $ 1 $ sticker. - Repeat drinking $ 1 $ bottled cola $ 3 $ times. Takahashi has $ 4 $ empty bottles and $ 1 $ sticker. - Make an exchange with $ i=2 $ , giving $ 4 $ empty bottles in exchange for $ 3 $ bottled colas and $ 1 $ sticker. Takahashi has $ 3 $ bottled colas and $ 2 $ stickers. - Repeat drinking $ 1 $ bottled cola $ 3 $ times. Takahashi has $ 3 $ empty bottles and $ 2 $ stickers. - Make an exchange with $ i=3 $ , giving $ 3 $ empty bottles in exchange for $ 1 $ bottled cola and $ 1 $ sticker. Takahashi has $ 1 $ bottled cola and $ 3 $ stickers. After these actions are completed, Takahashi has $ 3 $ stickers. No matter how he acts, he cannot obtain $ 4 $ or more stickers, so the answer is $ 3 $ . ### Sample Explanation 2 He can only drink the bottled colas he originally had. ### Constraints - $ 1\leq N \leq 10^{18} $ - $ 1\leq M \leq 2\times 10^5 $ - $ 1\leq B_i < A_i \leq 10^{18} $ - All input values are integers.