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: import sys
  
  input = sys.stdin.buffer.readline
  sys.setrecursionlimit(10**7)
  
  N = int(input())
  RC = [list(map(int, input().split())) for _ in range(N)]
  
  memo = [[-1] * (N + 1) for _ in range(N + 1)]
  inf = 10**18
  
  
  def mult(l, r):
      """
      半開区間[l, r)
      """
      if memo[l][r] != -1:
          return memo[l][r]
      if r - l <= 1:
          memo[l][r] = 0
          return 0
  
      res = inf
      for m in range(l + 1, r):
          prod = RC[l][0] * RC[m - 1][1] * RC[r - 1][1]
          tmp = mult(l, m) + mult(m, r) + prod
          res = min(res, tmp)
      memo[l][r] = res
      return res
  
  
  ans = mult(0, N)
  print(ans)
  
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"}]