P1853 投资的最大效益

投资的最大效益 P1853

例如：有如下两种不同的债券：

1. 投资额 $4000$，年利息 $400$；
2. 投资额 $3000$，年利息 $250$。

初始时，有 $10000$ 的总资产，可以投资两份债券 1 债券，一年获得 $800$ 的利息；而投资一份债券 1 和两份债券 2，一年可获得 $900$ 的利息，两年后，可获得 $1800$ 的利息；而所有的资产达到 $11800$，然后将卖掉一份债券 2，换购债券 1，年利息可达到 $1050$；第三年后，总资产达到 $12850$，可以购买三份债券 1，年利息可达到 $1200$，第四年后，总资产可达到 $14050$。

现给定若干种债券, 最初的总资产，帮助约翰先生计算，经过 $n$ 年的投资，总资产的最大值。

输入数据格式

第一行为三个正整数 $s, n, d$，分别表示最初的总资产, 年数和债券的种类。

接下来 $d$ 行，每行表示一种债券，两个正整数 $a, b$ 分别表示债券的投资额和年利息。

输出数据格式

仅一个整数，表示 $n$ 年后的最大总资产。

输入输出样例

输入 #1	输出 #1
10000 4 2 4000 400 3000 250	14050

说明与提示

对于 $100 \%$ 的数据，$1 \le s \le {10}^6$，$2 \le n \le 40$，$1 \le d \le 10$，$1 \le a \le {10}^4$，且 $a$ 是 $1000$ 的倍数，$b$ 不超过 $a$ 的 $10\%$。

*练习笔记

暂无人完成练习，做第一个完成练习的人—-first blood ！