题目背景

潮田 渚（Shiota Nagisa）因为理科不大好，自然会被仔细观察学生的杀老师发现，于是渚同学只得加入杀老师举办的课后期末考试滑溜滑溜补习班。至于为什么叫这个名字，额，你不能问我啊。

题目描述

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

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

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

当然的，杀老师也是有速度的啊，并且它想解决学生的一些问题，所以说杀老师最多只会跳过 $x-1$ 个学生，去解决下 $x$ 个学生的问题。

输入格式

第一行五个整数 $n,k,d,x,tp$，表示有 $n$ 个学生，只按顺序去到下一个学生的座位需要花费 $k$ 点精力，每多跳过一个学生就要多花费 $d$ 点精力值，每一次最多只能跳过 $x-1$ 个学生，是否是特殊数据。

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

• $tp=1$，第二行一个整数 $Seed$，作为种子，然后调用 $rnd$ 函数依次生成 $n$ 个整数，作为 $a$ 数组，$a_i$ 表示第 $i$ 个学生的问题的困难值为 $a_i$。

inline int rnd () {
	static const int MOD = 1e9;
	return Seed = ( 1LL * Seed * 0x66CCFF % MOD + 20120712 ) % MOD;
}

输出格式

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

5 3 4 1 0
1 2 3 4 5

27

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

717318

10000000 899999999 923456655 213111 1
1314520

9231813656566921

提示

样例解释 #1

杀老师每次不能跳过学生，因此他必须依次移动并解决所有问题，故答案为解决问题所需的精力 $1+2+3+4+5=15$ 与移动所需的精力 $4 \times 3=12$，所以花费精力之和为 $27$。

---

数据范围

本题采用捆绑测试。

• Subtask 1（20 points），学生们学习认真听话，留下来的同学也会更少：$tp=0$，$n \leq 10^3$。
• Subtask 2（30 points），杀老师的速度快极了，并且学生们没时间吐槽它：$tp=0$，$n \leq 10^6$。
• Subtask 3（50 points），$tp=1$，其余无特殊限制。

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

---

提示

对于 $tp=1$ 的数据，$rnd$ 函数只用于减小输入量，标准算法不依赖该数据生成方式。