直到约翰收到公证人的信，他才知道自己还有一个叔祖父。他从信中了解到，这位已故的叔祖父留下一大笔财产（在南美的某个地方），而约翰是唯一的继承人。

约翰现在不需要这么多的钱，不过他还是认为，最好的办法是把这些钱存到一个安全的地方，这样在他动用之前都可以一直增值。经过银行的一番说服，他现在对某种债券很感兴趣。

这种债券具有固定的价值，并给出了固定的年利息（在每年年底支付给所有者）。债券没有固定期限。债券还有不同的类型。价值较高的通常会产生更好的收益。不久，约翰意识到要找出债券的最优收益组合并不是一件容易的事情。而且，几年后，他的总资本会增长，到时候他必须重新安排他的债券组合（为了最优收益）。

假设以下债券可用：

如果有10000美元的起始资金，则可以购买两个价值4000美元的债券，每年的利息为800美元。当然，还有更好的购买方案，比如购买两个3000美元的债券和一个4000美元的债券，这样年利息可以达到900美元。

两年后，总资本已经增长到11800美元，这时我们可以出售3000美元的债券和再买入4000美元的债券，这样年利息可以增长到1050美元。（这个故事中有一个现实中不可能发生的事情：对于债券的买卖，银行不收取任何手续费）。下一年的总金额是12850美元，这样我们可以拥有三个4000美元的债券，每年的利息为1200美元。

你的问题是，给你一定数量起始资金、年数、一组可选债券的价值和年利息，请回答在最优的买卖策略下，最终的可以获得的最大资产。

第一行包含一个正整数 $N$ ，表示测试数据的组数。对于每一组测试数据：

第一行有两个正整数：起始资金（不超过 $1000000$ ），以及可用年数（不超过 $40$ ）。

接下来一行包含一个正整数 $d$ ($1 \leqslant d \leqslant 10$) ，表示可选的债券种数。

接下来的 $d$ 行，每一行有两个正整数，表示一种债券的描述。分别为债券的价值（保证为 $1000$ 的倍数），以及这种债券的年利息（不超过价值的 $10\%$ ）。

对于每一组测试数据，输出对应的在最优买卖策略下，最终可以获得的最大资金数。

1
10000 4
2
4000 400
3000 250

14050

原网页见POJ2063。