题目描述
小美有一笔财产，他想把这笔钱投入到纸人军团的银行进行投资以获得更大的效益。
纸人军团的银行发行了多种债券，每一种债券都能在固定的投资后，提供稳定的年利息。当然，每一种债券的投资额是不同的，一般来说，投资越大，收益也越大。而且，每一年还可以根据资金总额的增加，更换收益更大的债券。
例如：有如下两种不同的债券：
①投资额4000，年利息400；
②投资额3000，年利息250。
初始时，有10000的总资产，
可以投资两份债券①债券，一年获得800的利息；
而投资一份债券①和两份债券②，一年可获得900的利息，
两年后，可获得1800的利息；
当所有的资产达到11800，然后将卖掉一份债券②，换购债券①，年利息可达到1050；
第三年后，总资产达到12850，可以购买三份债券①，年利息可达到1200，第四年后，总资产可达到14050。
现给定若干种债券、最初的总资产，帮助小美计算，经过n年的投资，总资产的最大值。
输入
第一行为三个正整数s,n,d，分别表示最初的总资产、年数和债券的种类。(s <= 10000, n <= 40, d <= 10)
接下来d行，每行表示一种债券，两个正整数a,b分别表示债券的投资额和年利息。(a <= 10000且a是1000的倍数，b不超过a的10%)
输出
仅一个整数，表示n年后的最大总资产。
样例输入
10000 4 2
4000 400
3000 250样例输出
14050