It's the day before the AP CS exam, and Chelsea realizes she has yet to finish her AP practice on collegeboard.org!

There are ~N~ quizzes she must complete, in order, from ~1~ to ~N~, with the ~i~-th quiz requiring a knowledge level of ~k_i~. To complete the quizzes, Chelsea can watch one of the AP videos to increase her knowledge level by ~1~.

She starts with a knowledge level of ~0~, and each video takes her ~M~ minutes to watch. However, as she doesn't have much time, Chelsea figures she could also google the answer to a quiz in ~G \times d~ minutes, where ~d~ is the difference between Chelsea's current knowledge level and the knowledge level required to complete the quiz.

Assuming the time it takes Chelsea to actually write a quiz is negligible, what is the minimum time for Chelsea to finish all the quizzes?

Constraints

~1 \le N, M, G, k_i \le 10^6~

Input Specification

The first line of input will contain ~3~ integers: ~N~, ~M~, and ~G~.

The next line will contain ~N~ integers, the ~i~-th integer representing the knowledge level required to complete the ~i~-th quiz.

Output Specification

Output one integer, the minimum time for Chelsea to finish all the quizzes. Note the answer may not fit in a 32-bit integer.

Sample Input

4 5 3
1 8 10 9

Sample Output

48

Sample Explanation

It can be proven it is most optimal for Chelsea to first watch an AP video to do the first quiz (raising her knowledge level to ~1~), then watch seven more videos to do the second quiz (raising her knowledge level to ~8~), then watch one final video (raising her knowledge level to ~9~) before googling the answer to the third quiz in ~3~ minutes. Note she does not need to spend any time on the fourth quiz.