题目描述

小 A 做了一个糖果色的梦，于是他打算买一些糖果送给他的 $n$ 个小朋友。

小 A 可以零售地购买糖果，也可以批发地购买糖果，他还可以批发地回收糖果。

• 零售地购买糖果：每次小 A 可以给一个小朋友购买一个糖果，这将会花费 $1$ 元；

• 批发地购买糖果：每次小 A 可以给连续且不少于 $k$ 个小朋友分别购买一个糖果，设小朋友的个数为 $l$，这将会花费 $l-B$ 元；

• 批发地回收糖果：每次小 A 可以给连续且不少于 $k$ 个小朋友分别收回一个糖果，这将会获得 $C$ 元；

第 $i$ 个小朋友都希望自己得到不少于 $a_i$ 个糖果。求小 A 满足所有小朋友的希望的最小代价。

输入格式

第一行输入两个正整数 $n$、$k$，表示小朋友数量、批发最少需要的小朋友数量。

接下来输入两个整数 $B$、$C$。

接下来一行 $n$ 个非负整数 $a_1,a_2,\cdots,a_n$，表示每个小朋友希望的糖果个数。

输出格式

输出一行一个整数，表示最小代价。

4 2
1 1
1 2 3 4

6

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

124

提示

样例 1 解释：

我们给 $[1,2]$ 小朋友批发分别购买 $1$ 个糖果，代价为 $1$；给 $[3,4]$ 小朋友批发分别购买 $3$ 个糖果，代价为 $3$；给 $2$ 小朋友单独购买糖果，代价为 $1$；给 $4$ 小朋友单独购买糖果，代价为 $1$。总共代价为 $6$。

对于 $20\%$ 数据，满足 $1\le k\le n\le 10$。

对于 $40\%$ 数据，满足空间限制为 512 MB。

对于 $100\%$ 数据，满足 $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$。