001 - オレンジの出荷 (Oranges)

問題

　あなたは Juicy Orange Industry 社を知っているだろうか? この会社の業務は美味しいオレンジを栽培して出荷することである．ここでは略して JOI 社と呼ぶ．
　JOI 社では，収穫された N 個のオレンジを箱詰めして出荷することになった．オレンジは工場にあるベルトコンベアの上に並べられており，ベルトコンベアの前から順番に 1 から N までの番号が付けられている．オレンジは大小さまざまであり，オレンジ i (1 ≤ i ≤ N) の大きさは A_i である．
　これらのオレンジを前から順番にいくつかの箱に分けて詰める．ひとつの箱には連続した番号のオレンジしか詰めることができない．
　ひとつの箱には最大で M 個までのオレンジを詰めることができる．ある箱にいくつかのオレンジを詰めるためにかかるコストは，箱に詰める最大のオレンジの大きさを a，箱に詰める最小のオレンジの大きさを b，箱に詰めるオレンジの個数を s としたときに，K + s × (a - b) で求めることができる．ここで，K は箱にかかるコストであり，すべての箱で共通の値である．
　適切な個数の箱を用意して，すべてのオレンジを適切に箱詰めすることで，箱詰めにかかるコストの総和をできるだけ小さくしたい．

課題

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

入力

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

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

出力

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

制限

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

• 1 ≤ N ≤ 20 000．
• 1 ≤ M ≤ 1 000．
• 0 ≤ K ≤ 1 000 000 000．
• 1 ≤ A_i ≤ 1 000 000 000 (1 ≤ i ≤ N)．
• M ≤ N．

小課題

小課題 1 [20 点]

• N ≤ 20 を満たす．

小課題 2 [50 点]

　以下の条件を満たす．

• N ≤ 2 000．
• M ≤ 100．

小課題 3 [30 点]

　追加の制限はない．

入出力例

入力例 1

6 3 6
1
2
3
1
2
1

出力例 1

21

　1 番目の箱にオレンジ 1 からオレンジ 3 までの 3 個のオレンジを詰め，2 番目の箱にオレンジ 4 からオレンジ 6 までの 3 個のオレンジを詰めると，箱詰めにかかるコストの総和は (6 + 3 × (3 - 1)) + (6 + 3 × (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 ビット符号付き整数の範囲に収まるとは限らないことに注意せよ．