オレンジの出荷(Oranges)

あなたはJuicy Orange Industry 社を知っているだろうか? この会社の業務は美味しいオレンジを栽培して出荷することである．ここでは略してJOI 社と呼ぶ．

JOI 社では，収穫された $N$ 個のオレンジを箱詰めして出荷することになった．オレンジは工場にあるベルトコンベアの上に並べられており，ベルトコンベアの前から順番に $1$ から $N$ までの番号が付けられている．オレンジは大小さまざまであり，オレンジ $i$ $(1 \leq i \leq N)$ の大きさは $A_i$ である．

これらのオレンジを前から順番にいくつかの箱に分けて詰める．ひとつの箱には連続した番号のオレンジしか詰めることができない．

ひとつの箱には最大で $M$ 個までのオレンジを詰めることができる．ある箱にいくつかのオレンジを詰めるためにかかるコストは，箱に詰める最大のオレンジの大きさを $a$，箱に詰める最小のオレンジの大きさを $b$，箱に詰めるオレンジの個数を $s$ としたときに，$K + s \times (a - b)$ で求めることができる．ここで，$K$ は箱にかかるコストであり，すべての箱で共通の値である．

適切な個数の箱を用意して，すべてのオレンジを適切に箱詰めすることで，箱詰めにかかるコストの総和をできるだけ小さくしたい．

課題

ベルトコンベア上に並んでいるオレンジの情報と，ひとつの箱に詰められるオレンジの個数の最大値および，箱にかかるコストが与えられたとき，箱詰めにかかるコストの総和の最小値を求めるプログラムを作成せよ．

入力

標準入力から以下の入力を読み込め．

• 1 行目には，3 個の整数 $N, M, K$ が空白を区切りとして書かれている．これは，オレンジが $N$ 個あり，ひとつの箱に詰められるオレンジの個数の最大値が $M$ であって，箱にかかるコストが $K$ であることを表す．
• 続く $N$ 行のうちの $i$ 行目 $(1 \leq i \leq N)$ には，整数 $A_i$ が書かれている．これは，オレンジ $i$ の大きさが $A_i$ であることを表す．

出力

標準出力に，箱詰めにかかるコストの総和の最小値を 1 行で出力せよ．

制限

すべての入力データは以下の条件を満たす．

• $1 \leq N \leq 20 000$
• $1 \leq M \leq 1 000$
• $0 \leq K \leq 1 000 000 000$
• $1 \leq A_i \leq 1 000 000 000$ $(1 \leq i \leq N)$
• $M \leq N$

入出力例

入力例1

6 3 6
1
2
3
1
2
1

出力例1

21

$1$ 番目の箱にオレンジ $1$ からオレンジ $3$ までの $3$ 個のオレンジを詰め，$2$ 番目の箱にオレンジ $4$ からオレンジ $6$ までの $3$ 個のオレンジを詰めると，箱詰めにかかるコストの総和は $(6+3 \times (3 - 1))+(6+3 \times (2 - 1)) = 21$ となる．

どのように詰めても箱詰めにかかるコストの総和が $21$ を下回ることはないので， $21$ を出力する．

入力例2

16 4 12
3
10
13
10
19
9
12
16
11
2
19
9
13
2
13
19

出力例2

164

$11$ 個の箱を用意して，それぞれの箱に前から順に $1$ 個，$3$ 個，$1$ 個，$1$ 個，$3$ 個，$1$ 個，$1$ 個，$2$ 個，$1$ 個，$1$ 個，$1$ 個のオレンジを詰めることで，箱詰めにかかるコストの総和が最小となる．

入力例3

16 6 14
19
7
2
15
17
7
14
12
3
14
5
10
17
20
19
12

出力例3

177

入力例4

10 1 1000000000
1
1
1
1
1
1
1
1
1
1

出力例4

10000000000

答えが32 ビット符号付き整数の範囲に収まるとは限らないことに注意せよ．