オレンジの出荷 (Oranges)

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

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

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

• \(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 点]

追加の制限はない．

JOI 2016 · JCIOI · CC BY-SA 4.0