A - Warehouse Package Inspection Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は、大きな倉庫で荷物の検品作業を担当しています。倉庫には一直線上に N 個の棚が並んでおり、それぞれ 1 から N までの番号が順に付けられています。棚 i から棚 j への移動には |i - j| \times D 分かかります。ここで D は隣接する棚の間の移動にかかる時間（分）を表す正の整数です。

各棚には検品すべき荷物が置かれており、棚 i の荷物を検品するのにかかる時間は T_i 分です。検品は棚の前に立ち止まって行う必要があり、移動しながら検品することはできません。また、ある棚の検品を終えてから次の棚への移動を開始するものとし、検品と移動を同時に行うことはできません。移動の途中で他の棚の前を通過することがありますが、通過しただけでは検品したことにはなりません。検品するためには、改めてその棚へ移動して立ち止まる必要があります。

高橋君は最初、棚 S の前にいます。最初に検品する棚は自由に選ぶことができます。高橋君は棚 S の前から最初に検品する棚まで移動し、そこで検品を行います。棚 S を最初に検品する場合は移動時間 0 分で直ちに検品を開始できます。

高橋君は N 個すべての棚の荷物をちょうど 1 回ずつ検品しなければなりません。検品する棚の順序は自由に決めることができます。最後の棚の検品を終えた時点で作業は完了し、元の位置に戻る必要はありません。

すべての棚の荷物を検品し終えるまでの合計時間（すべての移動時間とすべての検品時間の合計）の最小値を求めてください。

制約

  • 1 \leq N \leq 10^6
  • 1 \leq D \leq 10^9
  • 1 \leq S \leq N
  • 1 \leq T_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数である。

入力

N D S
T_1 T_2 \ldots T_N
  • 1 行目には、棚の個数を表す整数 N 、隣接する棚の間の移動時間を表す整数 D 、開始位置の棚番号を表す整数 S が、スペース区切りで与えられる。
  • 2 行目には、各棚の荷物を検品するのにかかる時間 T_1, T_2, \ldots, T_N が、スペース区切りで与えられる。

出力

すべての棚の荷物をちょうど 1 回ずつ検品するときの、合計時間（移動時間＋検品時間）の最小値を 1 行で出力せよ。

入力例 1

4 2 2
3 1 4 2

出力例 1

18

入力例 2

5 3 5
2 8 1 6 4

出力例 2

33

入力例 3

12 5 6
7 2 9 4 6 3 8 5 1 10 2 7

出力例 3

144

入力例 4

30 100000000 17
12 999999999 345678901 1 500000000 234567890 876543210 111111111 222222222 333333333 444444444 555555555 666666666 777777777 888888888 999999998 123456789 987654321 314159265 271828182 161803398 141421356 173205080 223606797 707106781 1000000000 42 424242424 606060606 808080808

出力例 4

18099415856

入力例 5

1 1000000000 1
1000000000

出力例 5

1000000000

Score : 266 pts

Problem Statement

Takahashi is in charge of inspecting goods in a large warehouse. In the warehouse, N shelves are lined up in a straight line, numbered 1 to N in order. Moving from shelf i to shelf j takes |i - j| \times D minutes, where D is a positive integer representing the travel time (in minutes) between adjacent shelves.

Each shelf has goods to be inspected, and inspecting the goods on shelf i takes T_i minutes. The inspection must be performed while standing in front of the shelf; it cannot be done while moving. Furthermore, Takahashi must start moving to the next shelf only after finishing the inspection of the current shelf; inspection and movement cannot be performed simultaneously. Although he may pass by other shelves during movement, merely passing by does not count as inspecting them. To inspect them, he must move to that shelf again and stop.

Takahashi is initially in front of shelf S. He can freely choose which shelf to inspect first. Takahashi moves from the front of shelf S to the first shelf to be inspected, and performs the inspection there. If he chooses to inspect shelf S first, he can start the inspection immediately with a travel time of 0 minutes.

Takahashi must inspect the goods on all N shelves exactly once. The order in which he inspects the shelves can be chosen freely. The work is complete once the inspection of the last shelf is finished, and he does not need to return to his starting position.

Find the minimum total time (the sum of all travel times and all inspection times) required to finish inspecting the goods on all shelves.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq D \leq 10^9
  • 1 \leq S \leq N
  • 1 \leq T_i \leq 10^9 (1 \leq i \leq N)
  • All input values are integers.

Input

N D S
T_1 T_2 \ldots T_N
  • The first line contains three space-separated integers: N, the number of shelves; D, the travel time between adjacent shelves; and S, the starting shelf number.
  • The second line contains N space-separated integers T_1, T_2, \ldots, T_N, representing the time required to inspect the goods on each shelf.

Output

Print the minimum total time (travel time + inspection time) to inspect the goods on all shelves exactly once in a single line.

Sample Input 1

4 2 2
3 1 4 2

Sample Output 1

18

Sample Input 2

5 3 5
2 8 1 6 4

Sample Output 2

33

Sample Input 3

12 5 6
7 2 9 4 6 3 8 5 1 10 2 7

Sample Output 3

144

Sample Input 4

30 100000000 17
12 999999999 345678901 1 500000000 234567890 876543210 111111111 222222222 333333333 444444444 555555555 666666666 777777777 888888888 999999998 123456789 987654321 314159265 271828182 161803398 141421356 173205080 223606797 707106781 1000000000 42 424242424 606060606 808080808

Sample Output 4

18099415856

Sample Input 5

1 1000000000 1
1000000000

Sample Output 5

1000000000