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

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

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

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

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

課題

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

制限

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

• 1 \leqq N \leqq 20\,000．
• 1 \leqq M \leqq 1\,000．
• 0 \leqq K \leqq 1\,000\,000\,000．
• 1 \leqq A_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N)．
• M \leqq N．

小課題

小課題 1 [20 点]

• N \leqq 20 を満たす．

小課題 2 [50 点]

以下の条件を満たす．

• N \leqq 2\,000．
• M \leqq 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 \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 ビット符号付き整数の範囲に収まるとは限らないことに注意せよ．