output_description: Print the minimum possible total cost.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N D
      A_1 A_2 ... A_N
attempt: # Union-Find ****0スタートなので注意！****
  class UnionFind:
      # 作りたい要素数（ノードの数）nで初期化
      # 使用するインスタンス変数の初期化
      def __init__(self, n):
          self.n = n
          # root[x]<0ならそのノードが根かつその値が木の要素数
          # rootノードでその木の要素数を記録する
          self.root = [-1] * (
              n
          )  # 元々はn+1になっていたが、nにした（n+1なら1スタートで使えるかもしれないが、Count_Trees()がおかしくなるのでやめた）
          # 木をくっつける時にアンバランスにならないように調整する
          self.rnk = [0] * (n)  # 元々はn+1になっていたが、nにした
  
      # ノードxのrootノードを見つける
      def Find_Root(self, x):
          if self.root[x] < 0:
              return x
          else:
              # ついでに経路圧縮（調べた辺を根に直接つなぎ直す）をかけておく
              self.root[x] = self.Find_Root(self.root[x])
              return self.root[x]
  
      # 木の併合、入力は併合したい集合に属する各ノード
      def Unite(self, x, y):
          # 入力ノードのrootノードを見つける
          x = self.Find_Root(x)
          y = self.Find_Root(y)
          # すでに同じ木に属していた場合、何もしないで返す
          if x == y:
              return
          # 違う木に属していた場合rnkを見てくっつける方を決める
          elif self.rnk[x] > self.rnk[y]:
              self.root[x] += self.root[y]  # 要素数を足す(根のrootは"-要素数")
              self.root[y] = x  # ノードyの親をx（新しい集合の根）とする
          else:
              self.root[y] += self.root[x]  # 要素数を足す
              self.root[x] = y
              # rnkが同じ（深さに差がない場合）は1増やす（根(rnk1)+繋げる集合のrnkということで、1増えることになる）
              if self.rnk[x] == self.rnk[y]:
                  self.rnk[y] += 1
  
      # xとyが同じグループに属するか判断
      def isSameGroup(self, x, y):
          return self.Find_Root(x) == self.Find_Root(y)
  
      # ノードxが属する木のサイズを返す（根ノードの.root[idx]を-符号を外して返すだけ
      def Count(self, x):
          return -self.root[self.Find_Root(x)]  # -符号を外す
  
      # 木の数（＝集合の数）を返す（根の数=rootに-符号を持つものの数を返すだけ）
      def Count_Trees(self):
          treecnt = 0
          for eachroot in self.root:
              if eachroot < 0:
                  treecnt += 1
          return treecnt
  
problem_description: Statement
  
  There are N cities in Republic of AtCoder. The size of the i-th city is A_{i}.
  Takahashi would like to build N-1 bidirectional roads connecting two cities so
  that any city can be reached from any other city by using these roads.
  
  Assume that the cost of building a road connecting the i-th city and the j-th
  city is |i-j| \times D + A_{i} + A_{j}. For Takahashi, find the minimum
  possible total cost to achieve the objective.
samples: [{"input": "3 1\n    1 100 1", "output": "106\n    \n\nThis cost can be achieved by, for example, building roads connecting City 1, 2\nand City 1, 3.\n\n* * *"}, {"input": "3 1000\n    1 100 1", "output": "2202\n    \n\n* * *"}, {"input": "6 14\n    25 171 7 1 17 162", "output": "497\n    \n\n* * *"}, {"input": "12 5\n    43 94 27 3 69 99 56 25 8 15 46 8", "output": "658"}]