Description

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?

Input Format

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 Format

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

5 1 3
1 0
1 2
1 4

9

Hint

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