题目描述

有一家神奇的可乐商店，该商店不直接售卖可乐，而是提供可乐空瓶与新瓶装可乐的兑换服务。

一开始，高桥君拥有 $N$ 瓶可乐，之后他可以重复进行以下任意一种操作（次数可为 $0$ 次）：

• 喝掉一瓶可乐：高桥君持有的瓶装可乐数量减 $1$，空瓶数量加 $1$ 。（如果行动前没有瓶装可乐，则无法进行此操作。）
• 进行兑换：选择一个 $1$ 到 $M$ 之间（包含 $1$ 和 $M$ ）的整数 $i$ ，将 $A_i$ 个空瓶交给可乐商店，作为交换，他可以得到 $B_i$ 瓶新的可乐以及 $1$ 枚纪念贴纸 。（如果行动前持有的空瓶数量小于 $A_i$，则不能选择这个 $i$ 。若不存在可选择的 $i$，则无法进行此操作。）

高桥君非常喜欢贴纸，在最优操作下，他最多能获得多少枚贴纸呢？

需要注意的是，高桥君一开始既没有空瓶，也没有贴纸。

输入格式

输入以如下格式从标准输入给出：

N M
A_1 B_1
A_2 B_2
...
A_M B_M

输出格式

输出一个整数作为答案。

输入示例1

5 3
5 1
4 3
3 1

输出示例1

3

样例1解释

考虑以下操作：

1. 初始时，高桥君有 $5$ 瓶可乐。
2. 重复喝掉 $1$ 瓶可乐的操作 $5$ 次，此时高桥君拥有 $5$ 个空瓶。
3. 选择 $i = 2$ 进行兑换，用 $4$ 个空瓶换得 $3$ 瓶可乐和 $1$ 枚贴纸。此时高桥君有 $3$ 瓶可乐、$1$ 个空瓶和 $1$ 枚贴纸。
4. 重复喝掉 $1$ 瓶可乐的操作 $3$ 次，此时高桥君有 $4$ 个空瓶和 $1$ 枚贴纸。
5. 再次选择 $i = 2$ 进行兑换，用 $4$ 个空瓶换得 $3$ 瓶可乐和 $1$ 枚贴纸。此时高桥君有 $3$ 瓶可乐和 $2$ 枚贴纸。
6. 重复喝掉 $1$ 瓶可乐的操作 $3$ 次，此时高桥君有 $3$ 个空瓶和 $2$ 枚贴纸。
7. 选择 $i = 3$ 进行兑换，用 $3$ 个空瓶换得 $1$ 瓶可乐和 $1$ 枚贴纸。此时高桥君有 $1$ 瓶可乐和 $3$ 枚贴纸。

完成这些操作后，高桥君拥有 $3$ 枚贴纸。无论高桥君如何操作，都无法获得 $4$ 枚或更多的贴纸，所以答案是 $3$ 。

输入示例2

3 3
5 1
5 1
4 2

输出示例2

0

样例2解释

高桥君只能喝掉最初持有的瓶装可乐，无法进行兑换操作，所以能获得的贴纸数为 $0$。

输入示例3

415 8
327 299
413 396
99 67
108 51
195 98
262 180
250 175
234 187

输出示例3

11

数据范围

• $1\leq N \leq 10^{18}$
• $1\leq M \leq 2\times 10^5$
• $1\leq B_i < A_i \leq 10^{18}$
• 所有输入值均为整数