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