Problem Description

Little A had a candy-colored dream, so he decided to buy some candies for his $n$ friends.

Little A can buy candies individually or in bulk, and he can also recycle candies in bulk.

• Buying candies individually: Each time Little A can buy one candy for one friend, which will cost $1$ yuan;

• Buying candies in bulk: Each time Little A can buy one candy for a consecutive group of at least $k$ friends, where the number of friends is $l$, which will cost $l-B$ yuan;

• Recycling candies in bulk: Each time Little A can take back one candy from a consecutive group of at least $k$ friends, which will earn $C$ yuan;

Each of the $i$-th friends hopes to receive at least $a_i$ candies. Find the minimum cost for Little A to fulfill all his friends' wishes.

Input Format

The first line contains two positive integers $n$ and $k$, representing the number of friends and the minimum number of friends required for bulk purchases.

The next line contains two integers $B$ and $C$.

The following line contains $n$ non-negative integers $a_1, a_2, \cdots, a_n$, representing the desired number of candies for each friend.

Output Format

Output a single integer, representing the minimum cost.

Sample Input and Output

Sample Input #1

4 2
1 1
1 2 3 4

Sample Output #1

6

Sample Input #2

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

Sample Output #2

124

Notes

Sample 1 Explanation:

We buy $1$ candy in bulk for friends $[1,2]$, costing $1$; buy $3$ candies in bulk for friends $[3,4]$, costing $3$; buy $1$ candy individually for friend $2$, costing $1$; buy $1$ candy individually for friend $4$, costing $1$. The total cost is $6$.

For $20\%$ of the data, $1 \le k \le n \le 10$.

For $40\%$ of the data, the space limit is 512 MB.

For $100\%$ of the data, $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$.

见题面 Input 部分

见题面 Output 部分