Description
作为唯一的继承人，科丁先生继承其叔叔的很多财产;但他意识到，需要把这笔资金存放在安全的地方，让它增值。
银行向科丁先生推荐一种债券，债券有固定的价值，并且利息固定、在每年年底付给所有人，债券没有固定期限。
债券有不同的大小，科丁先生发现要买一套最优的债券并不容易，特别是几年后，随着资本的增加，必须重新评估债券计划
假设以下债券可用：
债券值 年利息
4000 400个
3000 250个
10000英镑的资本，可买两张4000英镑的债券，年利息为800英镑。
如果买两张3000英镑的债券、加买一张4000英镑的债券比较好，因为它的年利息是900英镑。
两年后，资本金增长到11800英镑，便可以卖出3000英镑，买入4000英镑，因此年利息增长到1050英镑。再过一年的总额是12850英镑，相当于4000英镑的三倍，年利息是1200英镑。
这就是你的问题：给定一个开始金额、若干年数、以及一组有其价值和利益的债券，利用买卖债券的最佳时间表，找出该数额在给定时期内可能增长多少。
Input
第一行包含一个正整数N，表示测试用例的数量, 接下来是测试用例。
测试用例的第一行包含两个正整数：开始金额（最多1000000），资本最大增长年数（最多40年）。
下一行包含一个数字：可用债券种类d（1<=d<=10）。接下来的d行每一行都包含一种债券描述：债券的价值和债券的年利息。债券的价值总是1000英镑的倍数。债券的利息不超过其价值的10%。
Output
对于每个测试用例，在一个最优的买卖计划之后，输出其最后的资本金额。
1
10000 4
2
4000 400
3000 250