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?
~1 \le N, M, G, k_i \le 10^6~
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 one integer, the minimum time for Chelsea to finish all the quizzes. Note the answer may not fit in a 32-bit integer.
4 5 3 1 8 10 9
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.