Migrated from Lutece 2732 建设道路

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

图图国新建成了 $n$ 座城市，第 $i$ 座城市的人口数为 $A_i$。图图国王希望在这 $n$ 座城市之间建设 $n-1$ 条道路，使得任意两座城市都能通过道路相互到达。第 $i$ 座城市与第 $j$ 座城市之间建设道路的代价为 $\mid i-j \mid \times D+A_i+A_j$。请你告诉图图国王完成这个任务的最小代价。

Input

第一行两个整数，$n$ ，$D$ 。 第二行 $n$ 个整数，第 $i$ 个整数 $A_i$ 表示第 $i$ 座城市拥有 $A_i$ 个人口。

Output

一个整数表示最小代价。

Samples

3 1
1 100 1

106

6 14
25 171 7 1 17 162

497

Constraints

$1 \leq n \leq 10^5$；

$1 \leq D \leq 10^9$；

$1 \leq A_i \leq 10^9$；

Resources

2022 UESTC ICPC Training for Graph