← 返回题目列表

AtCoder · abc085_d

D. 武士刀投掷者

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

分数: 400 点

问题陈述

你出去散步,突然遇到了怪物。幸运的是,你有 N 武士刀(剑),武士刀 1,武士刀 2, …,武士刀 N,并且可以以任意顺序执行以下两种攻击:

  • 使用你拥有的一把武士刀。当你挥舞武士刀时 i (1 ≤ i ≤ N),怪物收到 a_i 点伤害。同一把武士刀可以使用任意多次。
  • 扔掉你拥有的一把武士刀。当你扔武士刀时 i (1 ≤ i ≤ N) 在怪物身上,它收到 b_i 点伤害,并且你失去了武士刀。也就是说,你不能再挥舞或投掷该武士刀。

当怪物受到的总伤害达到 H 点以上。至少需要多少次攻击才能将其彻底消灭?

约束

  • 1 ≤ N ≤ 10^5
  • 1 ≤ H ≤ 10^9
  • 1 ≤ a_i ≤ b_i ≤ 10^9
  • 所有输入值均为整数。

输入

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

N H
a_1 b_1
:
a_N b_N

输出

打印消灭怪物所需的最少攻击总数。


示例输入 1

1 10
3 5

示例输出 1

3

你有一把武士刀。运用它交易 3 点伤害,投掷会造成伤害 5 点伤害。通过使用它两次然后扔掉它,你将处理 3 + 3 + 5 = 11 总共3次攻击造成伤害,怪物消失。


示例输入 2

2 10
3 5
2 6

示例输出 2

2

除了上面的武士刀之外,你还有另一把武士刀。运用它交易 2 点伤害,投掷会造成伤害 6 点伤害。通过投掷两把武士刀,你将处理 5 + 6 = 11 两次攻击造成伤害,使怪物消失。


示例输入 3

4 1000000000
1 1
1 10000000
1 30000000
1 99999999

示例输出 3

860000004

示例输入 4

5 500
35 44
28 83
46 62
31 79
40 43

示例输出 4

9