1364:炉石传说

在炉石传说游戏中，每张卡牌有一定的召唤费用和伤害值。玩家在回合开始时拥有一定数量的法力水晶，当召唤卡牌时，会根据卡牌的召唤费用扣除玩家拥有的法力水晶。法力水晶不得扣减为负数。

目前玩家手上拥有m种卡牌，每种卡牌都有2张（即手上有2m张卡牌）.玩家还有一个技能，能通过消耗一个法力水晶，使某一种卡牌（2张）的攻击力上升a点，该技能最多只能施放一次，也可以选择不施放。

问：玩家利用当前有限的法力水晶召唤卡牌的最大伤害总和是多少？

多组案例。一个正整数n，表示案例的数量。（n<=20）

每组案例中，先是三个正整数b、m和a，其中b表示玩家法力水晶的数量，m表示卡牌的种类，a表示技能可提升某类卡牌的攻击力（b<=2000, m<=1000，a<=100）

然后是m个正整数数对(ci, di)，其中ci表示第i种卡牌的召唤费用，di表示第i种卡牌的伤害值。（1<=i<=m，ci<=50, di<=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