P1853 Maximum Investment Return

Mr. John received a large inheritance that he does not need for now, so he decided to invest it to obtain greater returns. The bank offered him multiple types of bonds. Each bond provides a fixed annual interest after a fixed investment. Of course, each bond requires a different investment amount. Generally, the larger the investment, the greater the return. Moreover, each year he can switch to higher-yield bonds according to the increase in his total funds.

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.

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 a single integer, the maximum total assets after $n$ years.

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