“建太空梯进入太空要1兆亿？”魔法学院的院长瞪大了眼睛。

“这只是基础设施的费用，后期还要……”墨老师掰着手指算。

“哎呀，现在地主也很穷啊，学院的钱批下来就这么多，你想办法用这笔钱在债券市场上获得最大收益吧。”院长皱着眉头。

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

第一个为一个整数M，表示有M组数据。

每组数据第一行有两个整数，表示初始资金(不超过50000)和年数n。

每组数据第二行为一个整数d(1 ≤ d≤10)，表示债券种类。

随后d行每行有两个整数，表示该债券的价值和年收益。年收益不会超过债券价值的10%。

所有数据不超过整型取值范围。

每组数据，输出n年后获得的最大收益。

1
10000 4
2
4000 400
3000 250

14050