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: import fileinput
  
  
  def solve_slimes(slimes):
      slime_union_table = [0] * len(slimes) * len(slimes)
      slime_cost_table = [0] * len(slimes) * len(slimes)
  
      for i in range(len(slimes)):
          slime_union_table[i] = slimes[i]
  
      for gap in range(1, len(slimes)):
          for li in range(len(slimes) - gap):
              split_size = slime_union_table[li] + slime_union_table[li + 1 + (gap - 1) * len(slimes)]
              slime_union_table[li + gap * len(slimes)] = split_size
  
              for split in range(0, gap):
                  split_cost = slime_cost_table[li + split * len(slimes)] + slime_cost_table[li + split + 1 + (gap - split - 1) * len(slimes)] + split_size
  
                  if slime_cost_table[li + gap * len(slimes)] == 0:
                      slime_cost_table[li + gap * len(slimes)] = split_cost
  
                  else:
                      slime_cost_table[li + gap * len(slimes)] = min(
                          split_cost,
                          slime_cost_table[li + gap * len(slimes)]
                      )
      return slime_cost_table[len(slimes) * (len(slimes) - 1)]
  
  
  inp = fileinput.FileInput()
  
  inp.readline()
  slimes = [int(v) for v in inp.readline().split()]
  
  print(solve_slimes(slimes)
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**)"}]