402582: GYM100812 I Dragon Delivers

I stood just in front of an enormous castle of black stone, and rain water flowed down its walls. From afar I could see a tall tower with a light in the top room of it. I felt Dragon was there. He always liked to be higher than others. Somewhere inside there was also an alchemical laboratory which produced Blue Tea. There it was packed and then delivered to customers all over the city, just like pizza or hamburgers.

Orders came via pigeon post at the moments of time t_i. One instant delivery of Tea cost Dragon d pieces of gold, but it could unite any number of previously received orders. Delay of every order cost c pieces of gold per unit of time. The system was adjusted and worked like a clockwork in order to minimize the total expenses for deliveries, and knights were submissively closing their eyes to it. Gold always was harmful to people's eyesight.

The first line contains three integers separated by spaces: n, d and c (1 ≤ n ≤ 10³, 1 ≤ d ≤ 10⁹, 1 ≤ c ≤ 10⁶) — the number of orders, the cost of one delivery and the cost of delay for one unit of time, correspondingly.

The second line contains n integers separated by spaces: t_i (0 ≤ t_i ≤ 10⁹) — the moments of time when the orders are received. It is guaranteed that the sequence of these moments is strictly increasing, that is, t_i < t_i + 1.

Output one integer — the minimal total cost of all deliveries.

3 3 2
2 5 7

9

3 3 1
2 5 6

7

In the first sample it's more profitable to deliver each of three orders at the moments when they are received, and in the second sample it's better to deliver the second order together with the third one.