描述

John 从未想过自己还有一位叔祖父，直到他收到公证处的来信。信中透露，他已故的叔祖父在南美某地积累了大量财富，而 John 是唯一的继承人。

John 目前并不需要这么多钱，但他意识到应该把这笔资金妥善存储，并让它增值，直到他决定退休。银行向他推荐了一种债券，认为这种投资方式很适合他。

这种债券具有固定面值，并每年向持有人支付固定利息。债券没有固定期限，且不同面值的债券提供的利率也不同——通常面值越大，利率越高。John 很快发现，如何选择最优的债券组合并不是一件简单的事。而且，几年后他的本金会增长，投资策略也需要重新调整。

假设有以下两种债券可供选择：

如果初始本金为 10,000 美元，可以购买两张 4,000 美元的债券，年利息为 800 美元。但更优的策略是购买两张 3,000 美元债券和一张 4,000 美元债券，这样年利息可达 900 美元。两年后，本金增长到 11,800 美元，此时可以卖出一张 3,000 美元债券并买入一张 4,000 美元债券，使年利息增至 1,050 美元。这里有一个不太现实的设定：银行不收取债券买卖手续费。第三年，总金额达到 12,850 美元，此时可以购买三张 4,000 美元债券，年利息变为 1,200 美元。

你的任务是： 给定初始本金、投资年限以及若干债券的面值和利息，计算在最优买卖策略下，资金在指定年限后的最大可能总额。

输入

• 第一行是一个正整数 $N$，表示测试用例的数量。
• 每个测试用例的第一行包含两个正整数：初始本金（不超过 1,000,000 美元）和投资年数（不超过 40 年）。
• 第二行是一个整数 $d$（$1 \leq d \leq 10$），表示可选的债券种类数。
• 接下来的 $d$ 行，每行描述一种债券，包含两个整数：债券面值（总是 1,000 美元的整数倍）和年利息（不超过面值的 10%）。

输出

对于每个测试用例，输出一行，表示在最优策略下投资期结束后的资金总额。

输入数据 1

1
10000 4
2
4000 400
3000 250

输出数据 1

14050

来源

2004 年西北欧地区竞赛