题目描述

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

假设有两种不同的债券： 投资额为 4000 元，年利息为 400 元； 投资额为 3000 元，年利息为 250 元。 初始时，总资产为 10000 元。 可以选择投资一份债券 1，一年获得 800 元利息；或者投资一份债券 1 和两份债券 2，一年获得 900 元利息， 两年后获得 1800 元利息；这时资产为 11800 元，将一份债券 2 卖掉，换购债券 1，年利息可达到 1050 元； 第三年后，总资产达到 12850 元，可以购买三份债券 1，年利息可达到 1200 元； 第四年后，总资产可达到 14050 元。

给定最初的总资产、年数和债券的种类，计算经过 n 年的投资后总资产的最大值。

输入格式

第 1 行包含三个正整数 s 、n、d，分别表示最初的总资产、年数和债券的种类。

接下来的 d 行，每行包含两个正整数 vi、wi，分别表示每种债券的投资额和年利息。

输出格式

1行，包含一个整数，表示 n 年后乌拉乎的最大总资产。

样例1

10000 4 2 
4000 400 
3000 250

14050

样例2

50000 5 3
1000 50
10000 1000
6000 450

79800

数据范围

1 ≤ s ≤ 1000000; 1 ≤ n ≤ 40； 1 ≤ d ≤ 10； 1000 ≤ vi ≤ 100000；

vi是1000的倍数，wi不超过vi的10%。