loj#P6798. 「ICPC World Finals 2020」任务游戏
「ICPC World Finals 2020」任务游戏
Description
To relax before competing in the ICPC World Finals, you have decided to play a computer game called Quests. You have played it a number of times already, and now you want to achieve a perfect playthrough -- to prepare for your perfect playthrough of the finals!
In the game, you have to complete a number of quests, and you earn experience points (XPs) for completing each one. The total number of XPs you have earned at any time determines your current level. You reach a new level for every XPs that you earn. Formally, your level at any time is the largest integer such that you have at least XPs.
Each quest is assigned a number of XPs and a target difficulty level . If you complete the quest when your level is at least , you earn XPs. However, if you complete the quest when your level is less than , you will earn XPs. The constant is an XP multiplier that results in a bonus for completing a quest when you are at a lower level than the recommended level .
You know all the quests and their respective and numbers by heart (and you know the numbers and as well -- you have played this game a lot). You are also skilled enough to complete any quest, regardless of its target difficulty level and your level. You want to complete all the quests in an order that will allow you to earn the largest possible number of XPs.
For example in the sample input, the maximum XPs you can earn is , which is done as follows. First complete the second quest (you earn XPs, because you are at level , and you completed a quest with target difficulty level ). Then complete the first quest (you earn XPs, because you are still at level , and the target difficulty level is ). With XPs, you are now level . Finally, complete the third quest (for which you earn XPs, without the multiplier, since you are already at level ).
Input
The first line of input contains three integers , , and , where is the number of quests in the game, is the number of XPs required to reach each level, and is the XP multiplier for completing a quest before reaching its target difficulty level.
Following that are lines, each of which contains two integers and describing one quest, where is the number of XPs you earn for completing that quest if you are at or above its target difficulty level and is the target difficulty level for that quest.
Output
Output the maximum possible number of XPs you could earn by finishing all the quests.
3 10 2
15 1
2 2
9 1
43