SP3964 MINVEST - Investment Money

就是你有一笔钱，你要将这笔钱去投资债券，现在有$d$种债券，每种债券都有一个价值和年收益，债券的价值是$1000$的倍数，问你如何投资在$n$年后的获得最大收益。

第一个为一个整数$M$，表示有$M$组数据。 每组数据第一行有两个整数，表示初始资金(不超过$50000$)和年数$n$。 每组数据第二行为一个整数d($1 le d \le 10$)，表示债券种类。 随后$d$行每行有两个整数，表示该债券的价值和年收益。年收益不会超过债券价值的$10%$。 **所有数据不超过整型取值范围。**

每组数据，输出n年后获得的最大收益。 【输入样例】 ``` 1 10000 4 2 4000 400 3000 250 ``` 【输出样例】 ``` 14050 ```