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: # E
  N, D = map(int, input().split())
  A_list = list(map(int, input().split()))
  
  # minimum spanning tree
  
  res = 0
  
  # Prim based
  B_list = [0] * N
  for i in range(N):
      B_list[i] = A_list[i] + D * i
  
  C_list = [0] * N
  for i in range(N):
      C_list[i] = A_list[i] + D * (N - i)
  
  # cummin seen from left
  B_cummmin = [0] * N
  R = B_list[N - 1]
  BA = N - 1
  for i in range(N - 1, -1, -1):
      if B_list[i] <= R:
          R = B_list[i]
          BA = i
      B_cummmin[i] = BA
  
  # cummin seen from right
  C_cummmin = [0] * N
  R = C_list[0]
  CA = 0
  for i in range(N):
      if C_list[i] <= R:
          R = C_list[i]
          CA = i
      C_cummmin[i] = CA
  
  # start from 0
  start = 0
  while start < N - 1:
      end = B_cummmin[start + 1]
      target = C_cummmin[start]
      res += D * (end - target) + A_list[target] + A_list[end]
      for i in range(start + 1, end):
          ds = D * (i - target) + A_list[target] + A_list[i]
          de = D * (end - i) + A_list[end] + A_list[i]
          res += min(ds, de)
      start = end
  
  print(res)
  
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"}]