约翰先生获得了一大笔遗产，他暂时还用不上这一笔钱，他决定进行投资以获得更大的效益。银行工作人员向他提供了多种债券，每一种债券都能在固定的投资后，提供稳定的年利息。当然，每一种债券的投资额是不同的，一般来说，投资越大，收益也越大，而且，每一年还可以根据资金总额的增加，更换收益更大的债券。

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

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 年后的最大总资产。

对于 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\%。

luogu