问题 4010 --仙剑奇侠传

4010: 仙剑奇侠传

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

在李逍遥,阿奴,赵灵儿和拜月教主的最后一战中,阿奴用回梦将拜月眠了k回合,此时李逍遥还有m点神。李逍遥每回合可以选择用法术攻击或者无尘剑普通攻击,其中李逍遥有n种法术,每一种法术都需要消耗一定的神,并打掉拜月一定的血量(只有使用法术所需要的神不大于李逍遥该回合现有的神才可以使用该法术),而使用无尘剑普通攻击不消耗神但可打掉拜月一定的血量(假设是s)。李逍遥每攻击一次就用掉一回合数。那么,在这k回合内李逍遥最多可以打掉拜月的多少血量?(不考虑阿奴和赵灵儿的攻击,也不考虑李逍遥中途加神的情况)

输入

第一行整数T,代表测试数据的个数
接着T组测试数据,每组的第一行四个非负整数k,m,n,s(定义上面已给出, k<=50 , m<=3000 , 0<n<=10000,0<s<=100)
接着n行,每行输入两个正整数ai,bi(ai<=1000,bi<=100),代表使用第i个法术打掉拜月的ai的血量并消耗bi的神

输出

一个整数,表示k回合内最多打掉拜月的血量

样例输入

2
1 100 2 30
100 100
500 50
2 100 2 30
100 100
500 50

样例输出

500
1000

提示

By ACShiryu

来源

 

[提交][状态]