A - Chef's Break Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は、レストランの厨房で働く料理人です。

今日、高橋君は N 個の食材を下ごしらえする必要があります。i 番目の食材を下ごしらえするのにかかる時間は T_i 秒です。高橋君は一度に 1 つの食材しか下ごしらえすることができません。

また、厨房のルールとして、高橋君は作業中にちょうど M 回の休憩を取らなければなりません。各休憩は R 秒かかります。休憩は任意の食材の下ごしらえを終えた直後にのみ取ることができます（最初の食材に取りかかる前や、最後の食材を終えた後には取れません）。

すべての食材を下ごしらえし、かつちょうど M 回の休憩を取るとき、作業開始から全作業完了までにかかる最小の合計時間を求めてください。なお、食材を下ごしらえする順番は自由に決めることができます。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq N - 1
  • 1 \leq R \leq 10^9
  • 1 \leq T_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数である

入力

N M R
T_1 T_2 \ldots T_N
  • 1 行目には、食材の個数を表す N 、休憩の回数を表す M 、1 回の休憩にかかる時間を表す R が、スペース区切りで与えられる。
  • 2 行目には、各食材を下ごしらえするのにかかる時間 T_1, T_2, \ldots, T_N が、スペース区切りで与えられる。

出力

すべての食材を下ごしらえし、ちょうど M 回の休憩を取るときの、最小の合計時間を 1 行で出力せよ。

入力例 1

3 1 5
10 20 30

出力例 1

65

入力例 2

5 2 10
3 7 2 8 5

出力例 2

45

入力例 3

10 4 1000000000
100 200 300 400 500 600 700 800 900 1000

出力例 3

4000005500

Score : 200 pts

Problem Statement

Takahashi is a chef working in a restaurant kitchen.

Today, Takahashi needs to prepare N ingredients. The time required to prepare the i-th ingredient is T_i seconds. Takahashi can only prepare one ingredient at a time.

Additionally, according to the kitchen rules, Takahashi must take exactly M breaks during his work. Each break takes R seconds. A break can only be taken immediately after finishing the preparation of any ingredient (breaks cannot be taken before starting the first ingredient or after finishing the last ingredient).

Find the minimum total time from the start of work to the completion of all work, when preparing all ingredients and taking exactly M breaks. Note that the order in which ingredients are prepared can be freely chosen.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq N - 1
  • 1 \leq R \leq 10^9
  • 1 \leq T_i \leq 10^9 (1 \leq i \leq N)
  • All inputs are integers

Input

N M R
T_1 T_2 \ldots T_N
  • The first line contains N representing the number of ingredients, M representing the number of breaks, and R representing the time for one break, separated by spaces.
  • The second line contains the times T_1, T_2, \ldots, T_N required to prepare each ingredient, separated by spaces.

Output

Output in one line the minimum total time when preparing all ingredients and taking exactly M breaks.

Sample Input 1

3 1 5
10 20 30

Sample Output 1

65

Sample Input 2

5 2 10
3 7 2 8 5

Sample Output 2

45

Sample Input 3

10 4 1000000000
100 200 300 400 500 600 700 800 900 1000

Sample Output 3

4000005500