投资的最大效益
题目背景
约翰先生获得了一大笔遗产,他暂时还用不上这一笔钱,他决定进行投资以获得更大的效益。银行工作人员向他提供了多种债券,每一种债券都能在固定的投资后,提供稳定的年利息。当然,每一种债券的投资额是不同的,一般来说,投资越大,收益也越大,而且,每一年还可以根据资金总额的增加,更换收益更大的债券。
题目描述
例如:有如下两种不同的债券:
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
10000 4 2
4000 400
3000 250
输出样例 #1
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\%$。