#920 Buying Ramen 2026

Statement

Statement language

There are $N$ ramen factories, numbered from $1$ to $N$ in order. Gyojun wants to buy exactly $A_i$ packages of ramen from factory $i$ .

In one purchase, he may choose at most $K$ consecutive factories and buy one package from each chosen factory. If he chooses $\ell$ factories, the purchase costs $B+(\ell-1)C$ won.

Find the minimum total cost of buying all the required ramen.

Input

The input is given in the following format:

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

Output

Print the minimum total cost.

Constraints

$1\le N\le 200\,000$
$1\le K\le N$
$0 \leq A_{i} \leq 10^{6}$ ().

Samples

Sample 1

Input

3 3 3 1
1 2 1

Output

8

Sample 2

Input

2 2 1 3
2 1

Output

3

Sample 3

Input

1 1 1000000 1
0

Output

0