Dynamic programming - linear

Journey from west to east

There are n cities standing on a straight line from west to east. The cities are numbered from 1 to n, in order from west to east. Each point on the line has its own one-dimensional coordinate, and the point closer to the east has a large coordinate. The coordinate of the i-th city is xi.

You are now in city 1, and want to visit all cities. You have two ways to travel:

  • Walk in a straight line. At the same time, your level of fatigue will increase by a units each time you move a distance of 1, regardless of the direction.
  • Teleport to any point you want. Your fatigue level will increase by b units, regardless of teleported distance.


First line contains three numbers n (2n105), a and b (1a, b109). Next line contains n integers x1, x2, ... , xn (1xi109). For all i (1in1) holds inequality xi < xi+1.


Print the lowest possible level of fatigue, at which you will visit all the cities.


Test 1.


From city 1 we go to 2-nd, then teleport to 3-rd. Then go to 4-th. The level of fatigue at the end will be equal to 2 * 1 + 5 + 2 * 2 = 11, what is the lowest possible.

Test 3.

Visit all cities, in any order, teleporting six times. The level of fatigue will be equal to 12, which is the lowest possible.

Time limit 1 second
Memory limit 128 MiB
Input example #1
4 2 5
1 2 5 7
Output example #1
Input example #2
6 3 7
1 3 6 10 11 13
Output example #2
Input example #3
7 1 2
24 35 40 68 72 99 103
Output example #3
Author Rashad Mammadov, Abutalib Namazov
Source Azərbaycan 2019: Yuxarı yaş olimpiada hazırlığı qrupuna seçim turu