Maximizing Rewards in the Game Show Scheduling Challenge

In this problem, each contestant is awarded an initial amount of \( m \) yuan. However, during the game show, several mini-games are announced. The contest period is divided into \( n \) time slots, and there are \( k \) mini-games in total. Each mini-game must be completed in exactly one time slot and must start at the beginning of a time slot. Each mini-game \( i \) has a deadline \( t_i \) (in time slots) and an associated penalty \( w_i \) (a positive integer) which will be deducted from the reward if the game is not completed before its deadline.

Since every mini-game is given, if a contestant does not finish a mini-game by its deadline, a penalty of \( w_i \) is applied, and the final reward will be reduced accordingly. However, note that the competition is fair – contestants can never end up with a negative amount of money; if deductions exceed the award, the final reward is 0.

The challenge is to determine the optimal order in which to complete the mini-games such that the final money you receive is maximized. Completing a mini-game before its deadline prevents its penalty from being applied. Since each mini-game takes exactly one time slot, you can complete at most one mini-game in each time slot.

Hint: Think of the problem as selecting a subset of mini-games to perform (subject to scheduling constraints) in order to avoid as much penalty as possible. The final reward can be computed as:

[ \text{Final Reward} = m + \sum_{i \in S} w_i - \sum_{i=1}^{k} w_i ]

where S is the set of mini-games you manage to complete on time. Use a greedy strategy with a min-heap to select the mini-games with the largest penalties while fulfilling the deadline constraints.

inputFormat

The input begins with a single line containing three integers m, n, and k where m is the initial amount of money awarded, n is the number of available time slots, and k is the number of mini-games announced.

This is followed by k lines, each containing two integers t_i and w_i representing the deadline (in time slots) for the i^th mini-game and the penalty to be deducted if the game is not completed on time.

outputFormat

Output a single integer representing the maximum amount of money the contestant can receive after optimally scheduling the mini-games. If the calculated result is negative, output 0 instead.

sample

100 3 3
3 60
1 20
2 30

100