← 返回题目列表

AtCoder · abc410_e

H. 连续战斗

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

分数: 450 点

问题陈述

高桥即将玩一场格斗游戏 N 怪物按顺序排列。最初,高桥 健康 is H 和他的 魔力 is M.

对于 i- 他所战斗的第一个怪物,他可以选择以下行动之一:

  • 不使用魔法进行战斗。只有当他的健康状况至少为 A_i,他的健康状况下降了 A_i 并且怪物被击败。
  • 使用魔法进行战斗。只有当他的魔力至少为 B_i,他的魔力减少了 B_i 并且怪物被击败。

当全部完成时游戏结束 N 怪物被击败或他无法采取任何行动时。游戏结束前他最多可以击败多少只怪物?

约束

  • 1 \leq N \leq 3000
  • 1 \leq H,M \leq 3000
  • 1 \leq A_i,B_i \leq 3000
  • 所有输入值均为整数。

输入

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

N H M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

输出

输出答案。


示例输入 1

4 10 14
5 8
5 6
7 9
99 99

示例输出 1

3

通过采取以下行动,高桥可以击败 游戏结束前 3 怪物。

  • 最初,他的健康状况是 10 他的魔力是 14.
  • 战斗 1不使用魔法的st怪物。他的健康状况下降 5,变得健康 5 和魔力 14.
  • 战斗 2不使用魔法的第一个怪物。他的健康状况下降 5,变得健康 0 和魔力 14.
  • 战斗 3使用魔法的rd怪物。他的魔力减少了 9,变得健康 0 和魔力 5.
  • 对于 4第一个怪物,他不能选择任何一个行动,所以游戏结束。

示例输入 2

3 3000 3000
3 3
3 3
3 3

示例输出 2

3

他也许能够击败所有怪物。


示例输入 3

10 8 8
2 2
2 3
2 2
1 2
2 3
1 2
3 3
3 2
3 1
3 2

示例输出 3

9