라면사기 2026

교준이네 집 주변에는 1번부터 $N$번까지 차례대로 번호가 붙은 라면 공장이 있다. 교준이는 $i$번 공장에서 정확히 $A_i$개의 라면을 구매하려고 한다.

교준이는 한 번의 구매에서 길이가 $K$ 이하인 연속한 공장들을 선택하고, 선택한 각 공장에서 라면을 하나씩 구매할 수 있다. 선택한 공장의 수가 $\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$ ().