题目描述

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

例如初始资金为10000，有两种债券，一种价值4000，年收益为400，一种价值3000，年收益为250。如果买两张价值4000的债券，年收益为800，但显然买两张价值3000的债券和一张价值4000的债券，年收益为900是更好的选择。这样两年后资金已经涨到11800。此时如果出售一张价值3000的债券，再买进一张价值4000的债券，年收益将涨到1050。

输入格式

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

每组数据第一行有两个整数，表示初始资金（不超过1000000）和年数n（不超过40）。

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

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

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

输出格式

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

1
10000 4
2
4000 400
3000 250

14050