解题思路

这是一个典型的动态规划问题。

由于怪兽必须按顺序处理，每只怪兽只有两种选择：

题目内容

在潘多拉星球上，有一群怪兽组成一道阵线，奥特曼必须按顺序与这些怪兽战斗。奥特曼有一个初始能量值 $E$ ，每个怪兽都有一个攻击力 $damage$ 和击败奖励 $reward$ （击败后奥特曼可以恢复相应的能量值）。

当奥特曼面对第 $i$ 个怪兽时，有以下选择：

如果当前能量值大于怪兽攻击力 $damage[i]$ ，奥特曼可以选择战斗，此时会先消耗掉 $damage[i]$ 点能量，然后增加 $reward[i]$ 点能量；
如果当前能量值小于或等于怪兽攻击力 $damage[i]$ ，奥特曼不能与该怪兽战斗（因为奥特曼剩余能量不能 $≤ 0$ ），此时只能跳过该怪兽；
无论能否打过，都选择跳过该怪兽，此时奥特曼不消耗也不增加能量；

奥特曼的目标是尽可能多的击败怪兽（即最大化击败数量），现在需要计算奥特曼最多能击败多少个怪兽。

注意：

约束条件：

整数，最多击败的怪兽数量。

输入

18
15 17 4 18
1 15 4 17

输出

说明

奥特曼初始能量为 $18$ ，然后按顺序与怪兽战斗：

输入

5
10 20 30
1 1 1

输出

说明

每个怪兽都打不过，输出 $0$ 。

输入

9
5 4 5
0 3 4

输出

说明

奥特曼初始能量为 $9$ ，然后按顺序与怪兽战斗：

最多打败 $2$ 个怪兽，输出 $2$ 。