303004 - 收益

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

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

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

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

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

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

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

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