Maximizing Bonus Points from Daily Incentives

Little W plans to exercise for ( m ) days but can only take at most ( n ) steps in total. An exercise app offers ( k ) incentive measures to encourage him to walk. Each incentive measure is described as follows:

"If on day ( p ) you complete ( q ) steps, then every subsequent step on day ( p ) will earn you an extra 1 point."

Note that these incentives stack – that is, one step can earn more than 1 bonus point if multiple incentives on the same day are activated.

On the ( p\text{-th} ) day, assume the incentive thresholds are ( q_1, q_2, \dots, q_r ) (possibly in any order). If Little W takes ( x ) steps on that day, he will gain a bonus of

[ S(x) = \sum_{i=1}^{r} \max(0, x - q_i) \quad \text{,} ]
subject to the condition that if ( x ) is not greater than ( q_i ), then that particular incentive does not contribute.

Little W can distribute his ( n ) steps arbitrarily among the ( m ) days. Determine the maximum bonus points he can earn.

Hint: Because each day’s bonus function is convex (with increasing marginal gains once thresholds are passed), the optimum is achieved by putting all ( n ) steps on a single day which gives the highest bonus.

inputFormat

The first line contains three integers ( m ), ( n ), and ( k ), where ( m ) is the number of days, ( n ) is the total number of steps available, and ( k ) is the number of incentive measures.

Each of the following ( k ) lines contains two integers ( p ) and ( q ), representing an incentive measure on day ( p ) with threshold ( q ). It is guaranteed that ( 1 \le p \le m ).

outputFormat

Output a single integer, the maximum bonus points Little W can obtain.

sample

2 10 2
1 5
2 2

8