A96803.fangz 补习班

在补习班上，因为多个学生会同时有提问需求，所以 fangz 会制造分身，用音速在教室里来回回答问题。

补习班上有 $n$ 个同学，他们每一个人都有一个问题。fangz 为了有序回答学生的问题，把所有学生排成了一列。第 $i$ 个学生的问题有一个困难值 $a_i$，fangz 回答第 $i$ 个学生的问题需要花费 $a_i$ 点精力。fangz 到了哪一个学生那里，就必须解决那名学生的问题。

• fangz 最开始会解决序列中第 $1$ 个同学的问题；
• fangz 最后会去解决第 $n$ 个同学的问题；
• 期间 fangz 一直向编号增大的方向移动，不能后退。

当 fangz 解决完当前编号为 $p$ 的学生后，准备去下一位学生那里，如果只是走到编号为 $p+1$ 的下一个学生，则需要花费 $k$ 点精力值。

特殊地，如果 fangz 想让自己轻松一点，可以不去下一个，而是直接去下两个、下三个……也就是从位置 $p$ 直接跳到位置 $q$（$q>p$）而不解决中间同学的问题。但是，被跳过的学生会在一旁疯狂吐槽，给 fangz 的心灵造成打击，于是这一跳总共要花费的精力变为

$$k + (q-p-1)\times d,$$

其中 $q-p-1$ 是被跳过的学生人数。

注意：当 $q = p+1$ 时，$q-p-1=0$，这一跳的精力消耗仍然是 $k$。也就是说，上面这个公式对所有合法的 $q>p$ 都适用。

当然，fangz 也想尽量解决一些同学的问题，所以他规定每次最多只能连续跳过 $x-1$ 个学生，也就是说，从位置 $p$ 最远只能跳到 $p+x$（如果不超过 $n$）。形式化地，每一步移动中，$q$ 需要满足

$$p+1 \le q \le \min(p+x,\,n).$$

总结一下：你需要安排一条从 $1$ 号学生到 $n$ 号学生的访问路线

$$1 = i_1 < i_2 < \dots < i_m = n,$$

每次从 $i_t$ 跳到 $i_{t+1}$，满足 $1 \le i_{t+1}-i_t \le x$，并且：

• 每访问到一名学生 $i_t$，就要额外花费 $a_{i_t}$ 点精力；
• 从 $i_t$ 跳到 $i_{t+1}$ 的移动精力为

  $$k + (i_{t+1}-i_t-1)\times d.$$

请你计算，fangz 为了从第 $1$ 个学生走到第 $n$ 个学生，解决完他所到之处所有学生的问题，最少需要花费多少精力。

第一行包含四个整数 $n,k,d,x$，表示：

• $n$：学生的总数量；
• $k$：每次向后移动到某个学生的基础精力消耗；
• $d$：每多跳过一个学生需要额外增加的精力；
• $x$：每一步最多可以跳过 $x-1$ 个学生（即每步最远可以从 $p$ 跳到 $p+x$）。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，其中 $a_i$ 表示第 $i$ 个学生的问题的困难值。

输出一行一个整数，表示 fangz 解决完第 $n$ 个同学的问题，最少需要花费多少精力。

数据范围

• $1 \leq n < 10^6$；
• $0 \leq k,d,a_i \leq 10^9$；
• $1 \leq x \leq n-1$；
• 输入中的所有数都是整数。

样例解释 1

这里 $x = 1$，所以 fangz 每次不能跳过学生，只能从 $1$ 依次走到 $2,3,4,5$。

• 解决所有问题的精力为 $1+2+3+4+5 = 15$；
• 一共移动 $4$ 次，每次花费 $k=3$，因此移动精力为 $4 \times 3 = 12$。

总精力消耗为 $15 + 12 = 27$。