← 返回题目列表

AtCoder · abc415_d

G. 获得许多贴纸

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

该问题的设置与问题G类似,与问题G的不同之处在于最大化的目标和一些约束。

有一家神秘的可乐店。 这家店不直接卖可乐,而是提供空可乐瓶和新瓶装可乐的兑换服务。

最初,高桥有 N 瓶装可乐,从现在开始,他可以选择并执行以下操作之一任意次数(可能为零):

  • 喝 1 他有瓶装可乐。他拥有的瓶装可乐数量减少了 1,空瓶数量增加 1。 (如果他在行动前没有瓶装可乐,则不能采取该行动。)
  • 选择一个整数 i 之间 1 和 M,包括在内。给予 A_i 空瓶到可乐店,领取 B_i 瓶装可乐和 1 纪念贴纸作为回报。 (他无法选择 i 使得他在行动之前拥有的空瓶数量小于 A_i。 如果没有 i 可以选择,他不能执行此操作。)

高桥喜欢贴纸。当他表现最佳时,他最多可以获得多少张贴纸?

他最初没有空瓶子,也没有贴纸。

约束

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

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

输出

将答案输出为整数。


示例输入 1

5 3
5 1
4 3
3 1

示例输出 1

3

考虑以下操作:

  • 最初,高桥有 5 瓶装可乐。
  • 重复饮酒 1 瓶装可乐 5 次。高桥有 5 空瓶子。
  • 进行交流 i=2,给予 4 空瓶换取 3 瓶装可乐和 1 贴纸。高桥有 3 瓶装可乐, 1 空瓶,以及 1 贴纸。
  • 重复饮酒 1 瓶装可乐 3 次。高桥有 4 空瓶子和 1 贴纸。
  • 进行交流 i=2,给予 4 空瓶换取 3 瓶装可乐和 1 贴纸。高桥有 3 瓶装可乐和 2 贴纸。
  • 重复饮酒 1 瓶装可乐 3 次。高桥有 3 空瓶子和 2 贴纸。
  • 进行交流 i=3,给予 3 空瓶换取 1 瓶装可乐和 1 贴纸。高桥有 1 瓶装可乐和 3 贴纸。

这些动作完成后,高桥已经 3 贴纸。 无论他如何行动,都无法获得 4 或更多贴纸,所以答案是 3.


示例输入 2

3 3
5 1
5 1
4 2

示例输出 2

0

他只能喝原来的瓶装可乐。


示例输入 3

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

示例输出 3

11