output_description: Print the minimum number of scalar multiplication in a line.
input_description: In the first line, an integer $n$ is given. In the following $n$ lines, the
  dimension of matrix $M_i$ ($i = 1...n$) is given by two integers $r$ and $c$
  which respectively represents the number of rows and columns of $M_i$.
attempt: global memo
  
  
  def find_memo(m, l):  # memoのm行l列の値を返す.data
      # data[l]から続くm+1個の要素からなる部分リスト
      if memo[m][l] != 0:
          return memo[m][l]
  
      if m < 2:
          return memo[m][l]
  
      tmp_min = 999999999
      for i in range(1, m):
          left = find_memo(i, l)
          right = find_memo(m - i, l + i)
          middle = memo[0][l] * memo[0][l + i] * memo[0][l + m]
          if left + right + middle < tmp_min:
              tmp_min = left + right + middle
      memo[m][l] = tmp_min
      return tmp_min
  
  
  tmp_min = 9999999999
  n = int(input())
  memo = [
      [0] * (n + 1 - i) for i in range(n + 1)
  ]  # memo[i][j]はdata[j]から続くi+1個の要素からなる部分リストの最小計算コストを表す
  
  memo[0][0], memo[0][1] = map(int, input().split())
  for i in range(2, n + 1):
      dummy, memo[0][i] = map(int, input().split())
  
  for i in range(n - 1):
      memo[2][i] = memo[0][i] * memo[0][i + 1] * memo[0][i + 2]
  
  print(find_memo(n, 0))
  
problem_description: Matrix-chain Multiplication
  
  The goal of the matrix-chain multiplication problem is to find the most
  efficient way to multiply given $n$ matrices $M_1, M_2, M_3,...,M_n$.
  
  Write a program which reads dimensions of $M_i$, and finds the minimum number
  of scalar multiplications to compute the maxrix-chain multiplication
  $M_1M_2...M_n$.
samples: [{"input": "6\n    30 35\n    35 15\n    15 5\n    5 10\n    10 20\n    20 25", "output": "15125"}]