题目描述

在补习班上，因为多个学生会同时有需求，所以杀老师会制造分身用音速移动来回回答问题。

补习班上有 $n$ 个同学，他们每一个人都有一个问题。杀老师为了有序回答学生的问题，把所有学生排成了一列。第 $i$ 个学生的问题有一个困难值 $a_i$，杀老师回答第 $i$ 个学生的问题需要花费 $a_i$ 的精力。杀老师到了哪里，它就要解决那个学生的问题。杀老师最开始会解决序列中第一个同学的问题，他最后会去解决最后一个同学的问题。

杀老师每次解决完一个同学的问题到下一个同学的座位上就要花费 $k$ 点精力值。特殊的，如果杀老师想让自己轻松一点，可以不移动到下一个，可以直接到下两个，下三个，就不用解决跳过的同学的问题了。对应的，它会被学生调侃。受到打击的杀老师自然会花费格外的精力，花费的精力为 $k+(q-p-1) \times d$（当前位置为 $p$，跳到的位置为 $q$）。

杀老师可以跳过任意数量的学生。

输入格式

第一行三个整数 $n,k,d$，表示有 $n$ 个学生，只按顺序去到下一个学生的座位需要花费 $k$ 点精力，每多跳过一个学生就要多花费 $d$ 点精力值。

第二行 $n$ 个整数 $a_{1\dots n}$，$a_i$ 表示第 $i$ 个学生的问题的困难值为 $a_i$。

输出格式

一行一个整数，表示杀老师解决完最后一个同学的问题最少需要花费多少精力。

5 3 4
1 2 3 4 5

21

10 30630 56910
7484 99194 86969 17540 29184 68691 91892 81564 93999 74280 

558934

数据范围

对于 $100\%$ 的数据，$1 \leq n \leq 10^6$，$0 \leq k,d,a_i \leq 10^9$。