(本题和补习班1仅有数据范围不一样)

题目描述

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

补习班上有 $n$ 个同学，他们每一个人都有一个问题。杀老师为了有序回答学生的问题，把所有学生排成了一列。第 $i$ 个学生的问题有一个困难值 $a_i$，杀老师回答第 $1$ 个学生的问题需要花费 $a_1$ 的精力。之后可以跳过若干个学生，设之前解决问题的学生编号为$j$，之后解决问题的学生编号为$i$，则解决编号为$i$的学生花费的精力为$(a[i]-a[j])*k-d$,$k$和$d$为给定的常数。杀老师最开始会解决序列中第一个同学的问题，他最后会去解决最后一个同学的问题。求杀老师最少花费的精力,注意花费的精力可能为负数。

输入格式

第一行三个整数 $n,k,d$。

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

输出格式

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

5 3 4
1 2 3 4 5

-3

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

2045456774

数据范围

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