Problem Description

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.

Input Format

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 Format

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

4 2
1 1
1 2 3 4

6

10 5
1 3
1 1 4 5 1 4 1 9 19 81

124

Hint

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