分数: 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