LGTB 最近在玩一个类似DOTA 的游戏名叫THD
有一天他在守一座塔，对面的N 个小兵排成一列从近到远站在塔前面
每个小兵有一定的血量hi，杀死后有一定的金钱gi
每一秒，他都可以攻击任意一个活着的小兵，对其造成P 点伤害，如果小兵的血量低于1 点，小兵死亡，他
得到金钱。他也可以不攻击任何小兵。
每一秒LGTB 攻击完毕之后，塔会攻击距离塔最近的一个活着的小兵，对其造成Q 点伤害，如果小兵的血
量低于1 点，小兵死亡，LGTB 不会得到金钱
现在LGTB 想知道，在他选择最优策略时，他能得到多少钱。
输入
输入第一行包含3 个整数P, Q, N
接下来N 行，每行包含2 个整数hi, gi
第i 个小兵和塔之间的距离为i
输入的意义如题面所示
对于20% 的数据，$1 \leqslant N \leqslant 4$
对于50% 的数据，$1 \leqslant N \leqslant 20$
对于100% 的数据，$20 \leqslant P, Q \leqslant 200$, $1 \leqslant N \leqslant 100$, $1 \leqslant h_{i} \leqslant 200$, $1 \leqslant g_{i} \leqslant 10^{6}$
输出
输出包含一个整数W，代表LGTB 最多能获得的金钱
样例
样例输入样例输出
20 60 3
80 100
80 200
120 300
500
4
假如我们要得到第$i$个士兵的收益，我们可以贪心地让塔打小兵尽量多的次数，然后让LGTB去补刀。当然这样不一定一次能打死，所以需要在补刀之前还需打上几次。
所以用$f[i][j]$表示当前考虑到第$i$个士兵时（前面的士兵已经被消灭了），当前积攒了$j$次攻击机会时的最大收益，
第一种操作是不管这个小兵，那么直接让塔把它打死，那么就可以得到一些攻击机会。
第二种操作是在塔把它打残后补刀，这样会消耗一些攻击机会，同时会得到一些收益。
Code
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("thd.in");
ofstream fout("thd.out");
typedef class xb{
public:
int money; //钱数
int health; //生命值
int kill;
int pkill;
}xb;
int p,q,n;
xb *xbs;
int f[][];
istream& operator >>(istream& in, xb& x){
in>>x.health>>x.money;
}
int main(){
fin>>p>>q>>n;
xbs = new xb[(const int)(n + )];
for(int i = ; i <= n; i++){
fin>>xbs[i];
xbs[i].kill = ( xbs[i].health - )/q; //塔把士兵i打成残血的次数
xbs[i].pkill = ( xbs[i].health - xbs[i].kill * q - )/p + ; //塔把士兵打成残血后，玩家打死士兵的次数
}
for(int i = ;i <= n;i++){ //f数组初始化
for(int j =; j <= ;j++){
f[i][j] = -;
}
}
f[][] = ;
for(int i = ; i <= n;i++){
for(int j = ;j <= ;j++){
f[i][j + xbs[i].kill + ] = max(f[i - ][j], f[i][j + xbs[i].kill + ]);
if(j >= xbs[i].pkill - xbs[i].kill){
f[i][j - (xbs[i].pkill - xbs[i].kill)] = max(f[i - ][j] +
xbs[i].money, f[i][j - (xbs[i].pkill - xbs[i].kill)]);
}
}
}
int maxv = f[n][];
for(int i = ;i <= ;i++)
maxv = max(f[n][i], maxv);
fout<<maxv;
return ;
}