P6023 Walking

Xiao W downloaded a fitness app.

Xiao W plans to work out over the next $m$ days. Since he cannot walk too much and get exhausted (how could that happen), over these $m$ days he can walk at most $n$ steps in total. To encourage Xiao W to walk, the app provides $k$ incentive rules. Each rule is of the form: “If on day $p$ you finish walking $q$ steps, then on day $p$ every subsequent step will give you an additional $1$ point.” **Incentive rules can stack, meaning that for one step you may gain more than $1$ point.** Now Xiao W wants to know: what is the maximum total number of points he can get?

The first line contains three integers $n,m,k$, with meanings as above. The next $k$ lines each contain two integers $p,q$, describing an incentive rule as above.

Output one integer, the maximum points that can be obtained after $m$ days.

Explanation for the sample: There is only one plan: walk $5$ steps on the first day. The first and second steps each gain $1$ point, the third and fourth steps each gain $2$ points, and the fifth step gains $3$ points, for a total of $9$ points. Constraints: For $10\%$ of the testdata, $n,m,k \le 10$. For $40\%$ of the testdata, $n,m,k \le 10^3$. For $100\%$ of the testdata, $1 \le n \le 10^{12}$, $1 \le m,k \le 10^5$, $1 \le p \le m$, $0 \le q \le n$. Translated by ChatGPT 5