AT_abc410_e [ABC410E] Battles in a Row
题目描述
高桥在玩游戏,他要**按顺序**对战 $N$ 只怪兽,初始时,高桥有 $H$ 点体力和 $M$ 点魔力。
对于第 $i$ 只怪兽,高桥可以选择:
- 使用体力战斗,当且仅当高桥当前体力 $\ge A_i$ 时可以选择,高桥花费 $A_i$ 点体力击败第 $i$ 只怪兽。
- 使用魔力战斗,当且仅当高桥当前魔力 $\ge B_i$ 时可以选择,高桥花费 $B_i$ 点魔力击败第 $i$ 只怪兽。
当高桥面对某只怪兽时无法进行上述任意一种战斗或所有 $N$ 只怪兽均被击败时,游戏结束。求他最多能击败多少只怪兽。
输入格式
第一行三个整数 $N,H,M(1\le N,H,M\le 3000)$。\
接下来 $N$ 行,每行两个整数 $A_i,B_i(1\le A_i,B_i\le 3000)$ 描述高桥要击败的第 $i$ 只怪兽。
输出格式
输出一行一个整数表示答案。
说明/提示
**样例 1 解释**
高桥可以击败 $3$ 只怪兽,一种可能的进程如下:
- 初始时,高桥有 $10$ 点体力和 $14$ 点魔力。
- 对于第一只怪兽,高桥使用体力战斗,剩余 $5$ 点体力和 $14$ 点魔力。
- 对于第二只怪兽,高桥使用体力战斗,剩余 $0$ 点体力和 $14$ 点魔力。
- 对于第三只怪兽,高桥使用魔力战斗,剩余 $0$ 点体力和 $5$ 点魔力。
- 对于第四只怪兽,高桥无法进行战斗,游戏结束。
**样例 2 解释**
高桥可以击败所有的 $N$ 只怪兽。
By @[chenxi2009](/user/1020063)