#P1240. 补习班2

补习班2

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

题目描述

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

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

输入格式

第一行三个整数 n,k,dn,k,d

第二行 nn 个整数 a1na_{1\dots n}aia_i 表示第 ii 个学生的问题的困难值为 aia_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%100\% 的数据,1n1061 \leq n \leq 10^60k,d,ai1060 \leq k,d,a_i \leq 10^6