#arc067b. [arc067_b]Walk and Teleport
[arc067_b]Walk and Teleport
Problem Statement
There are towns on a line running east-west. The towns are numbered through , in order from west to east. Each point on the line has a one-dimensional coordinate, and a point that is farther east has a greater coordinate value. The coordinate of town is .
You are now at town , and you want to visit all the other towns. You have two ways to travel:
-
Walk on the line. Your fatigue level increases by each time you travel a distance of , regardless of direction.
-
Teleport to any location of your choice. Your fatigue level increases by , regardless of the distance covered.
Find the minimum possible total increase of your fatigue level when you visit all the towns in these two ways.
Constraints
- All input values are integers.
- For all , .
Input
The input is given from Standard Input in the following format:
Output
Print the minimum possible total increase of your fatigue level when you visit all the towns.
Sample Input 1
4 2 5
1 2 5 7
Sample Output 1
11
From town , walk a distance of to town , then teleport to town , then walk a distance of to town . The total increase of your fatigue level in this case is , which is the minimum possible value.
Sample Input 2
7 1 100
40 43 45 105 108 115 124
Sample Output 2
84
From town , walk all the way to town . The total increase of your fatigue level in this case is , which is the minimum possible value.
Sample Input 3
7 1 2
24 35 40 68 72 99 103
Sample Output 3
12
Visit all the towns in any order by teleporting six times. The total increase of your fatigue level in this case is , which is the minimum possible value.