あなたは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 行で出力せよ.
すべての入力データは以下の条件を満たす.
6 3 6 1 2 3 1 2 1
21
$1$ 番目の箱にオレンジ $1$ からオレンジ $3$ までの $3$ 個のオレンジを詰め,$2$ 番目の箱にオレンジ $4$ からオレンジ $6$ までの $3$ 個のオレンジを詰めると,箱詰めにかかるコストの総和は $(6+3 \times (3 - 1))+(6+3 \times (2 - 1)) = 21$ となる.
どのように詰めても箱詰めにかかるコストの総和が $21$ を下回ることはないので, $21$ を出力する.
16 4 12 3 10 13 10 19 9 12 16 11 2 19 9 13 2 13 19
164
$11$ 個の箱を用意して,それぞれの箱に前から順に $1$ 個,$3$ 個,$1$ 個,$1$ 個,$3$ 個,$1$ 個,$1$ 個,$2$ 個,$1$ 個,$1$ 個,$1$ 個のオレンジを詰めることで,箱詰めにかかるコストの総和が最小となる.
16 6 14 19 7 2 15 17 7 14 12 3 14 5 10 17 20 19 12
177
10 1 1000000000 1 1 1 1 1 1 1 1 1 1
10000000000
答えが32 ビット符号付き整数の範囲に収まるとは限らないことに注意せよ.