Description

For example, consider the following two types of bonds:

1. Investment amount $4000$, annual interest $400$.
2. Investment amount $3000$, annual interest $250$.

Initially, with a total of $10000$ in assets, he can invest in two units of Bond 1 and earn $800$ in interest in one year. Alternatively, investing in one unit of Bond 1 and two units of Bond 2 yields $900$ in interest in one year; after two years, the total interest is $1800$, bringing total assets to $11800$. Then, by selling one unit of Bond 2 and switching to Bond 1, the annual interest can reach $1050$. After the third year, total assets reach $12850$, at which point he can purchase three units of Bond 1, yielding an annual interest of $1200$. After the fourth year, total assets reach $14050$.

Given several types of bonds and the initial total assets, help Mr. John compute the maximum possible total assets after $n$ years of investment.

Input Format

The first line contains three positive integers $s, n, d$, representing the initial total assets, the number of years, and the number of bond types, respectively.

The next $d$ lines each describe one type of bond. Each line contains two positive integers $a, b$, representing the investment amount and the annual interest of the bond, respectively.

Output Format

Output a single integer, the maximum total assets after $n$ years.

10000 4 2
4000 400
3000 250

14050

Hint

For $100\%$ of the testdata, $1 \le s \le {10}^6$, $2 \le n \le 40$, $1 \le d \le 10$, $1 \le a \le {10}^4$, $a$ is a multiple of $1000$, and $b$ does not exceed $10\%$ of $a$.

Translated by ChatGPT 5