题目背景

唐僧师徒四人西天取经途中积累了一笔丰厚的功德值。师徒四人暂时还用不上这些功德值，他们决定进行投资以获得更大的收益。天界的工作人员向他们提供了多种功德债券，每一种功德债券都能在固定的投资后，提供稳定的年利息。当然，每一种功德债券的投资额是不同的，一般来说，投资越大，收益也越大。而且，每一年还可以根据资金总额的增加，更换收益更大的债券。供稳定的年利息。当然，每一种债券的投资额是不同的，一般来说，投资越大，收益也越大，而且，每一年还可以根据资金总额的增加，更换收益更大的债券。

题目描述

例如：有如下两种不同的功德债券：
①投资额4000，年利息400；
②投资额3000，年利息250。
初始时，有10000的总功德值，可以投资两份债券①债券，一年获得800的利息；而投资一份债券①和两份债券②，一年可获得900的利息，两年后，可获得1800的利息；而所有的资产达到11800，然后将卖掉一份债券②，换购债券①，年利息可达到1050；第三年后，总功德值达到12850，可以购买三份债券①，年利息可达到1200，第四年后，总功德值可达到14050。
现给定若干种功德债券、最初的总功德值，帮助唐僧师徒计算，经过 n 年的投资，总功德值的最大值。

输入格式：

第一行为三个正整数 s、n、d，分别表示最初的总功德值、年数和功德债券的种类。
接下来 d 行，每行表示一种功德债券，两个正整数 a、b 分别表示功德债券的投资额和年利息。

输出格式：

仅一个整数，表示 n 年后的最大总功德值。

输入样例#1：

10000 4 2
4000 400
3000 250

输出样例#1：

14050

数据范围：

s≤10^6，n≤40，d≤10，a≤10^4,且a是1000的倍数，b不超过a的10%。