output_description: Print the minimum possible total cost incurred.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      a_1 a_2 \ldots a_N
attempt: n = int(input())
  a = [int(x) for x in input().strip().split()]
  
  c = [[None for i in range(n)] for j in range(n)]
  s = [[0 for i in range(n)] for j in range(n)]
  
  for i in range(n):
      c[i][i] = 0
      s[i][i] = a[i]
  
  for i in range(n):
      for j in range(i + 1, n):
          s[i][j] = s[i][j - 1] + a[j]
  
  
  def solve(i, j):
      if c[i][j] is not None:
          return c[i][j]
      mn = 10**10
      for k in range(i, j):
          mn = min(mn, solve(i, k) + solve(k + 1, j) + s[i][k] + s[k + 1][j])
      c[i][j] = mn
      return c[i][j]
  
  
  # print(s)
  print(solve(0, n - 1))
  # print(c)
  
problem_description: Statement
  
  There are N slimes lining up in a row. Initially, the i-th slime from the left
  has a size of a_i.
  
  Taro is trying to combine all the slimes into a larger slime. He will perform
  the following operation repeatedly until there is only one slime:
  
    * Choose two adjacent slimes, and combine them into a new slime. The new slime has a size of x + y, where x and y are the sizes of the slimes before combining them. Here, a cost of x + y is incurred. The positional relationship of the slimes does not change while combining slimes.
  
  Find the minimum possible total cost incurred.
samples: [{"input": "4\n    10 20 30 40", "output": "190\n    \n\nTaro should do as follows (slimes being combined are shown in bold):\n\n  * (**10** , **20** , 30, 40) \u2192 (**30** , 30, 40)\n  * (**30** , **30** , 40) \u2192 (**60** , 40)\n  * (**60** , **40**) \u2192 (**100**)\n\n* * *"}, {"input": "5\n    10 10 10 10 10", "output": "120\n    \n\nTaro should do, for example, as follows:\n\n  * (**10** , **10** , 10, 10, 10) \u2192 (**20** , 10, 10, 10)\n  * (20, **10** , **10** , 10) \u2192 (20, **20** , 10)\n  * (20, **20** , **10**) \u2192 (20, **30**)\n  * (**20** , **30**) \u2192 (**50**)\n\n* * *"}, {"input": "3\n    1000000000 1000000000 1000000000", "output": "5000000000\n    \n\nThe answer may not fit into a 32-bit integer type.\n\n* * *"}, {"input": "6\n    7 6 8 6 1 1", "output": "68\n    \n\nTaro should do, for example, as follows:\n\n  * (7, 6, 8, 6, **1** , **1**) \u2192 (7, 6, 8, 6, **2**)\n  * (7, 6, 8, **6** , **2**) \u2192 (7, 6, 8, **8**)\n  * (**7** , **6** , 8, 8) \u2192 (**13** , 8, 8)\n  * (13, **8** , **8**) \u2192 (13, **16**)\n  * (**13** , **16**) \u2192 (**29**)"}]