AT_keyence2019_e Connecting Cities
题目描述
有 $n$ 个点排成一行，在第 $i,j$ 个点之间连边的代价为 $|i-j| \times D+A_i+A_j$，求将它们连成一棵树的最小代价。
$1 \leq n \leq 2\times 10^5$，$1 \leq D,A_i \leq 10^9$
输入格式
第一行两个整数 $n,D$。
第二行 $n$ 个整数 $A_1,A_2,\dots,A_n$。
输出格式
输出一个整数表示答案。
说明/提示
### 制約
- $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $
- $ 1\ \leq\ D\ \leq\ 10^9 $
- $ 1\ \leq\ A_{i}\ \leq\ 10^9 $
- $ A_{i},\ D $ は整数
### Sample Explanation 1
例えば，都市 $ 1 $ と都市 $ 2 $ の間と，都市 $ 1 $ と都市 $ 3 $ の間に道路を建設することで，このコストを達成することができます．