2016-17 Woburn Challenge Finals Round - Senior Division

It would seem that war is inevitable. Bo Vine's communication with his cow spy has been intercepted by the devious monkeys, confirming his suspicions that the Head Monkey is up to no good! In preparation for the impending conflict with the monkeys, Bo Vine has ordered the construction of a new, state-of-the-art Cow-Bot model from scratch.

The schematics call for ~N~ ~(1 \le N \le 200\,000)~ different modules to be installed, in any order. Bo Vine's cow engineers require ~E~ ~(1 \le E \le 10\,000)~ minutes to install any single module. However, the Cow-Bot (being a sophisticated, artificially intelligent piece of hardware) may also be able to help out! If at least ~M_i~ ~(0 \le M_i \le N)~ different modules have already been installed into the Cow-Bot up to a certain point in time, then it becomes able to install the ~i~-th module into itself in ~B~ ~(1 \le B \le 10\,000)~ minutes. Only one module may be in the process of being installed into the Cow-Bot at any time, meaning that the engineers and Cow-Bot may not simultaneously install two different modules at once.

Please help the cows determine the minimum amount of time required for all ~N~ modules to be installed into the Cow-Bot.

In test cases worth ~7/9~ of the points, ~N \le 2\,000~.

Input Specification

The first line of input consists of three space-separated integers ~N~, ~E~, and ~B~.
~N~ lines follow, the ~i~-th of which consists of a single integer ~M_i~ (for ~i = 1 \dots N~).

Output Specification

Output one line consisting of a single integer – the minimum number of minutes required for all ~N~ modules to be installed into the Cow-Bot.

Sample Input

7 7 4
4
0
4
2
6
4
4

Sample Output

34

Sample Explanation

One optimal sequence of module installations is as follows (with each step's completion time indicated):

• Module ~2~ by the Cow-Bot (~4~ minutes)
• Module ~3~ by the engineers (~11~ minutes)
• Module ~7~ by the engineers (~18~ minutes)
• Module ~4~ by the Cow-Bot (~22~ minutes)
• Module ~6~ by the Cow-Bot (~26~ minutes)
• Module ~1~ by the Cow-Bot (~30~ minutes)
• Module ~5~ by the Cow-Bot (~34~ minutes)