魔兽争霸

时间限制:1000 ms 内存限制:65536 KB

总提交:226 (74 users) 正确提交:72 (56 users)

描述

小赖正在无聊的玩着魔兽争霸…

游戏的主人公有n个魔法, 每个魔法分为若干个等级，第i个魔法有p[i]个等级(不包括0), 每个魔法的每个等级都有一个效果值，一个j级的i种魔法的效果值为w[i][j], 魔法升一级需要一本相应的魔法书, 购买魔法书需要金币，第i个魔法的魔法书价格为c[i], 而小赖只有m个金币(为了积攒rp, 这次他没用修改器)

你的任务就是帮助小赖决定如何购买魔法书才能使所有魔法的效果值之和最大，开始时所有魔法为0级 效果值为0。

输入

第一行一个整数T 表示有T组数据

对于每组数据：

第一行 用空格隔开的两个正整数n, m (nv;

for(int i=1;i>tmpc>>p[i];

for(int j=1;j>tmptmp;

get[i][j]=get[i][j-1]+tmptmp;

cost[i][j]=cost[i][j-1]+tmpc;

}

}

for(int i=1;i=0;--j)

{

tmpmaxget=0;

tmpmaxcost=0;

for(int k=0;k=0)

{

if(get[i][k]>tmpmaxget)

{

tmpmaxcost=j-cost[i][k];

tmpmaxget=get[i][k];

}

else if(tmpmaxget==get[i][k]&&tmpmaxcost