题目描述

你有 $n$ 个城市，你需要建立 $n-1$ 条边将其联通。

连接任意两点 $i,j$ 都有边，其边权为 $a_i+a_j+d\cdot |i-j|$。

你需要求最小的边权和满足条件。

输入格式

第一行两个整数 $n,d$。

第二行 $n$ 个整数 $a_i$。

输出格式

一个整数表示答案。

样例输入

4 10
1 100 200 5

样例输出

362

数据范围

本题设有subtask。

对于所有数据，满足 $n\leq 2\cdot 10^5, 1\leq d,a_i\leq 10^9$

subtask1(30)，$n\leq 5000$

subtask2(30)，$d,a_i\leq 2\cdot 10^5$

subtask3(40)，无特殊限制。

时间限制：$\texttt{1s}$

空间限制：$\texttt{512M}$