| 问题描述 |
|---|
在炉石传说游戏中，每张卡牌有一定的召唤费用和伤害值。 玩家在回合开始时拥有一定数量的法力水晶，当召唤卡牌时，会根据卡牌的召唤费用扣除玩家拥有的法力水晶，但是法力水晶不得扣减为负数。 目前玩家拥有$$m$$个法力水晶以及$$n$$种卡牌，每种卡牌都有$$2$$张（即手上有$$2n$$张卡牌）。 玩家还有一个技能，能通过消耗一个法力水晶，使某一种卡牌（$$2$$张）的攻击力上升$$a$$点，该技能最多只能施放一次，也可以选择不施放。 问：玩家利用当前有限的法力水晶召唤卡牌的最大伤害总和是多少？ |
| 输入描述 |
一个正整数$$T$$表示案例的数量。 每组案例中，先是三个正整数$$m,n,a$$，其中$$m$$表示玩家法力水晶的数量，$$n$$表示卡牌的种类，$$a$$表示技能可提升某类卡牌的攻击力。 然后是$$n$$个正整数数对$$(c_i, d_i)$$，其中$$c_i$$表示第$$i$$种卡牌的召唤费用，$$d_i$$表示第$$i$$种卡牌的伤害值。 数据约束：$$T \le 20、m \le 2000、n \le 1000、a \le 100、c_i \le 50、d_i \le 100$$ |
| 输出描述 |
针对每组案例，输出一个整数，表示玩家召唤卡牌的最大伤害总和。 |
| 样例输入复制样例 |
2 10 2 1 4 5 5 7 10 2 3 4 5 5 7 |
| 样例输出 |
14 16 |
| 提示说明 |
第一组案例，召唤$$2$$张$$5$$费用的卡牌，伤害$$7+7=14$$ 第二组案例，使用技能强化$$4$$费用的卡牌，使之攻击力提升到$$5+3=8$$，然后召唤$$2$$张$$4$$费用的卡牌，伤害$$8+8=16$$ |
| 相关 |