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)