P10889 [Bad Problem Cup Round 1] A Candy-Colored Dream

Little A had a candy-colored dream, so he decided to buy some candies for his $n$ children. Little A can buy candies at retail, buy candies in bulk, and also recycle candies in bulk. - Retail purchase: Each time, Little A can buy one candy for one child, which costs $1$ yuan. - Bulk purchase: Each time, Little A can buy one candy for each child among a consecutive segment of at least $k$ children. Let the number of children be $l$; this costs $(l - B)$ yuan. - Bulk recycling: Each time, Little A can take back one candy from each child among a consecutive segment of at least $k$ children, and he will earn $C$ yuan. The $i$-th child hopes to receive at least $a_i$ candies. Find the minimum cost for Little A to satisfy all children.

The first line contains two positive integers $n$ and $k$, representing the number of children and the minimum number of children required for a bulk operation. Then two integers $B$ and $C$ are given. The next line contains $n$ non-negative integers $a_1, a_2, \cdots, a_n$, representing the number of candies each child hopes to receive.

Output one integer on one line, representing the minimum cost.

**Explanation for Sample 1:** We bulk-buy $1$ candy for each child in $[1,2]$, with cost $1$. We bulk-buy $3$ candies for each child in $[3,4]$, with cost $3$. We buy candies separately for child $2$, with cost $1$. We buy candies separately for child $4$, with cost $1$. The total cost is $6$. **Constraints:** For $20\%$ of the testdata, $1 \le k \le n \le 10$. For $40\%$ of the testdata, the memory limit is at least 512 MB. For $100\%$ of the testdata, $1 \le k \le n \le 1000$, $0 \le B \le k$, $0 \le C \le k - B$, $0 \le a_i \le 10^9$. The memory limit is at least 10 MB. Translated by ChatGPT 5