Time for some video games!

Bob is playing a video game with ~N~ levels, where the boss on the ~i~-th level has a power of ~A_i~. Bob initially has no power. In order to clear a level, Bob needs to have at least as much power as the boss on that level. Also, Bob may only attempt level ~i~ after clearing all levels ~j~ with ~j < i~.

Thankfully, Bob can power up! He can spend ~H~ seconds to gain ~1~ unit of power permanently by increasing his HP, or he can spend ~P~ seconds to drink a potion, also netting him ~1~ unit of power but only for the next boss fight. He may perform either of these actions at any point and as many times as he wants.

Bob wants to clear all the levels. How long does he need?

Constraints

~1 \le N, H, P, A_i \le 10^6~

Subtask 1 [30%]

~1 \le N \le 3 \times 10^3~

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line will contain three space-separated integers, ~N~, ~H~ and ~P~.

The next line will contain ~N~ space-separated integers ~A_i~.

Output Specification

Output a single integer, the minimum time Bob needs to spend to beat all the bosses.

Sample Input

3 5 3
1 3 20

Sample Output

66

Explanation

It can be proven that it is optimal to first increase Bob's HP by ~1~ unit, beat the boss on the first level, increase Bob's HP by ~2~ more units, beat the boss on the second level, and finally drink potions in order to beat the boss on the third level, for a total of ~66~ seconds.