ラーメン購入 2026

$1$ から $N$ まで順に番号が付いたラーメン工場がある。ギョジュンは工場 $i$ からラーメンをちょうど $A_i$ 個購入したい。

1 回の購入では、連続する $K$ 個以下の工場を選び、選んだ各工場からラーメンを 1 個ずつ購入できる。選んだ工場の数が $\ell$ のとき、費用は $B+(\ell-1)C$ ウォンである。

必要なラーメンをすべて購入するための最小費用を求めよ。

入力は次の形式で与えられる。

$N\ K\ B\ C$ $A_1\ A_2\ \cdots\ A_N$

最小費用を出力せよ。

• $1\le N\le 200\,000$
• $1\le K\le N$
• $0\le A_i\le 10^6$ ().