A7073 | 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$ 个同学的问题，最少需要花费多少精力。