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: import numpy as np
  
  InputData1 = input()
  InputData2 = input()
  
  Lines = [data.split(" ") for data in [InputData1, InputData2]]
  InputNumbers = [int(numbers) for line in Lines for numbers in line]
  
  N = InputNumbers[0]
  D = InputNumbers[1]
  A = InputNumbers[2:]
  # print(N, D, A)
  
  
  def NetworkMatrix(Num, vector):
      matrix = np.empty((Num, Num))
      for i in range(Num):
          ai = np.empty(Num)
          for j in range(Num):
              if i < j:
                  aij = (j - i) * D + vector[i] + vector[j]
              else:
                  aij = 0
              ai[j] = aij
          matrix[i] = ai
      return matrix
  
  
  def Explore(Num, matrix):
      ResultMatrix = matrix
      for i in range(Num):
          # ResultVector[i] = min(matrix.T[i])
          for j in range(Num):
              for k in range(Num):
                  if i < j < k and min([matrix[i, j], matrix[j, k], matrix[i, k]]) != 0:
                      if matrix[i, j] >= matrix[j, k] and matrix[i, j] >= matrix[i, k]:
                          ResultMatrix[i, j] = 0
                      elif matrix[j, k] > matrix[i, j] and matrix[j, k] >= matrix[i, k]:
                          ResultMatrix[j, k] = 0
                      elif matrix[i, k] > matrix[i, j] and matrix[i, k] > matrix[j, k]:
                          ResultMatrix[i, k] = 0
      if np.sum(ResultMatrix != matrix) != 0:
          ResultMatrix = Explore(Num, matrix)
      return ResultMatrix
  
  
  Matrix = NetworkMatrix(N, A)
  # print(Matrix)
  # Raveled = Matrix.ravel()
  # Answer = sum(sorted(Raveled)[:N-1])
  AnswerMatrix = Explore(N, Matrix)
  # print(AnswerMatrix)
  print(int(np.sum(AnswerMatrix)))
  
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"}]