AtCoder Beginner Contest 052

D - Walk and Teleport


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 500

問題文

東西方向にのびる直線上に、N 個の町があります。 町には、西から順に 1 から N までの番号がついています。 直線上には座標が設定されていて、東に行くほど座標が大きくなります。 町 i の座標は X_i です。

あなたは今、町 1 にいて、これからほかの全ての町を訪れたいです。 移動する手段は次の 2 種類あります。

  • 直線上を歩いて移動する。 東西どちらに歩いても、1 移動する度に疲労度が A 上がります。

  • 好きな場所へテレポートする。 テレポートをすると、移動した距離によらず疲労度が B 上がります。

この 2 種類の移動を繰り返して全ての町を最適に回った時、疲労度の上昇値の合計の最小値がいくつになるか求めてください。

制約

  • 入力は全て整数である
  • 2≦N≦10^5
  • 1≦X_i≦10^9
  • 全ての i(1≦i≦N-1) について、X_i<X_{i+1} が成り立つ
  • 1≦A≦10^9
  • 1≦B≦10^9

入力

入力は以下の形式で標準入力から与えられる。

N A B
X_1 X_2 ... X_N

出力

全ての町を最適に回った時、疲労度の上昇値の合計の最小値がいくつになるかを出力せよ。


入力例 1

4 2 5
1 2 5 7

出力例 1

11

1 から町 2 まで 1 の距離歩いて移動したあと、町 3 にテレポートし、そこから町 4 まで 2 の距離歩いて移動すると、 疲労度の上昇値の合計が 2×1+5+2×2=11 になり、これが最小です。


入力例 2

7 1 100
40 43 45 105 108 115 124

出力例 2

84

1 から町 7 まで歩き続けると、疲労度の上昇値の合計が 84 になり、これが最小です。


入力例 3

7 1 2
24 35 40 68 72 99 103

出力例 3

12

どのような順番でもよいので、6 回のテレポートで全ての町を訪れると、疲労度の上昇値の合計が 12 になり、これが最小です。

Score : 500 points

Problem Statement

There are N towns on a line running east-west. The towns are numbered 1 through N, 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 i is X_i.

You are now at town 1, and you want to visit all the other towns. You have two ways to travel:

  • Walk on 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 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.
  • 2≤N≤10^5
  • 1≤X_i≤10^9
  • For all i(1≤i≤N-1), X_i<X_{i+1}.
  • 1≤A≤10^9
  • 1≤B≤10^9

Input

The input is given from Standard Input in the following format:

N A B
X_1 X_2 ... X_N

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 1, walk a distance of 1 to town 2, then teleport to town 3, then walk a distance of 2 to town 4. The total increase of your fatigue level in this case is 2×1+5+2×2=11, 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 1, walk all the way to town 7. The total increase of your fatigue level in this case is 84, 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 12, which is the minimum possible value.


Submit提出する