P6040 「ACOI2020」课后期末考试滑溜滑溜补习班

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

在补习班上，因为多个学生会同时有需求，所以杀老师会制造分身用音速移动来回回答问题。 补习班上有 $n$ 个同学，他们每一个人都有一个问题。杀老师为了有序回答学生的问题，把所有学生排成了一列。第 $i$ 个学生的问题有一个困难值 $a_i$，杀老师回答第 $i$ 个学生的问题需要花费 $a_i$ 的精力。杀老师到了哪里，它就要解决那个学生的问题。杀老师最开始会解决序列中第一个同学的问题，他最后会去解决最后一个同学的问题。 杀老师每次解决完一个同学的问题到下一个同学的座位上就要花费 $k$ 点精力值。特殊的，如果杀老师想让自己轻松一点，可以不移动到下一个，可以直接到下两个，下三个，就不用解决跳过的同学的问题了。对应的，它会被学生调侃。受到打击的杀老师自然会花费格外的精力，花费的精力为 $k+(q-p-1) \times d$（当前位置为 $p$，跳到的位置为 $q$）。 当然的，杀老师也是有速度的啊，并且它想解决学生的一些问题，所以说杀老师最多只会跳过 $x-1$ 个学生，去解决下 $x$ 个学生的问题。

无

无

#### 样例解释 #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$ 函数只用于减小输入量，标准算法不依赖该数据生成方式。