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 vv XPs that you earn. Formally, your level at any time is the largest integer LL such that you have at least LvL \cdot v XPs.

Each quest is assigned a number xx of XPs and a target difficulty level dd. If you complete the quest when your level is at least dd, you earn xx XPs. However, if you complete the quest when your level is less than dd, you will earn cxc \cdot x XPs. The constant cc is an XP multiplier that results in a bonus for completing a quest when you are at a lower level than the recommended level dd.

You know all the nn quests and their respective xx and dd numbers by heart (and you know the numbers vv and cc 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 4343, which is done as follows. First complete the second quest (you earn 44 XPs, because you are at level 00, and you completed a quest with target difficulty level 22). Then complete the first quest (you earn 3030 XPs, because you are still at level 00, and the target difficulty level is 11). With 3434 XPs, you are now level 33. Finally, complete the third quest (for which you earn 99 XPs, without the multiplier, since you are already at level 33).

Input

The first line of input contains three integers nn, vv, and cc, where nn (1n2000)(1 \leq n \leq 2\,000) is the number of quests in the game, vv (1v2000)(1 \leq v \leq 2\,000) is the number of XPs required to reach each level, and cc (2c2000)(2 \leq c \leq 2\,000) is the XP multiplier for completing a quest before reaching its target difficulty level.

Following that are nn lines, each of which contains two integers xx and dd describing one quest, where xx (1x2000)(1 \leq x \leq 2\,000) is the number of XPs you earn for completing that quest if you are at or above its target difficulty level and dd (1di106)(1 \leq d_i \leq 10^6) 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