P10889 【烂题杯 Round 1】糖果色的梦

小 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$，表示每个小朋友希望的糖果个数。

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

**样例 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$。满足内存限制至少为 10 MB。