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: def main():
      import sys
  
      input = sys.stdin.readline
  
      class UnionFind:
          def __init__(self, n):
              self.n = n
              self.root = [-1] * (n + 1)
              self.rnk = [0] * (n + 1)
  
          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):
              x = self.find_root(x)
              y = self.find_root(y)
              if x == y:
                  return
              elif self.rnk[x] > self.rnk[y]:
                  self.root[x] += self.root[y]
                  self.root[y] = x
              else:
                  self.root[y] += self.root[x]
                  self.root[x] = y
                  if self.rnk[x] == self.rnk[y]:
                      self.rnk[y] += 1
  
          def isSameGroup(self, x, y):
              return self.find_root(x) == self.find_root(y)
  
          def size(self, x):
              return -self.root[self.find_root(x)]
  
      N, D = map(int, input().split())
      A = list(map(int, input().split()))
  
      A_plus = [0] * N
      A_minus = [0] * N
      for i in range(N):
          A_plus[i] = A[i] + D * i
          A_minus[i] = A[i] - D * i
  
      edge = []
      m = float("inf")
      m_idx = 0
      for i in range(N - 1):
          if A_minus[i] < m:
              m = A_minus[i]
              m_idx = i
          edge.append((m_idx + 1, i + 2, A_plus[i + 1] + A_minus[m_idx]))
      m = float("inf")
      m_idx = 0
      for i in range(N - 1, 0, -1):
          if A_plus[i] < m:
              m = A_plus[i]
              m_idx = i
          edge.append((m_idx + 1, i, A_plus[m_idx] + A_minus[i - 1]))
  
      edge.sort(key=lambda x: x[2])
      UF = UnionFind(N + 1)
      ans = 0
      for u, v, cost in edge:
          if UF.isSameGroup(u, v):
              continue
          ans += cost
          UF.unite(u, v)
      print(ans)
  
  
  if __name__ == "__main__":
      main()
  
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"}]