There are
N cities on the east-west line. Cities are numbered from
1 to
N in order from west to east. Each point on the line has one-dimensional coordinates, and the point further east has the larger coordinate value. City coordinate
i -
Xi. You are in city
1 and want to visit all other cities. You have two ways to travel:
- Walk along the line. Your fatigue level increases by
A each time you travel a distance of
1, regardless of direction.
- Teleport to any location of your choice. Your fatigue level increases by
B regardless of the distance traveled.
Find the lowest possible total increase in your fatigue level when you visit all the cities in these two ways.
Input
The first line contains three integers
N (
\(2<=N<=10^5\)),
A< /code> (\(1<=A<=10^9\)), B (\(1<=B<=10^9\)). The second line contains the coordinates of cities Xi (\(1<=X_i<=10^9\) ), for all i \(X_i <X_{i+1}\)( \(1<=i<=N-1\)).
Imprint
Display the answer to the problem.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
4 2 5
1 2 5 7
| 11 |
From city 1, travel distance 1 to city 2, then teleport to city 3, then travel distance 2 to city 4.
The total increase in your fatigue level in this case is 2 x; 1 + 5 + 2 x 2 = 11, which is the smallest possible value. |
| 2 |
7 1 100
40 43 45 105 108 115 124
| 84 |
From city 1, walk to city 7.
The total increase in your fatigue level in this case is 84, which is the lowest possible value. |
| 3 |
7 1 2
24 35 40 68 72 99 103
| 12 |
Visit all cities in any order by teleporting six times.
The total increase in fatigue level in this case is 12, which is the lowest possible value. |