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: # dp[i][j] - minimum cost from i to j
  
  INF = 1e18 + 5
  
  n = int(input())
  
  arr = [int(x) for x in input().split()]
  
  dp = [[0 for _ in range(n)] for _ in range(n)]
  
  
  def range_sum(arr, L, R):
      s = 0
      for i in range(L, R + 1):
          s += arr[i]
      return s
  
  
  for L in reversed(range(n)):
      for R in range(L, n):
          if L == R:
              dp[L][R] = 0
          else:
              dp[L][R] = INF
              s = range_sum(arr, L, R)
              # try every possible middle
              for mid in range(L, R):
                  dp[L][R] = min(dp[L][R], dp[L][mid] + dp[mid + 1][R] + s)
  
  print(dp[0][n - 1])
  
  """
  
  int main() {
      const int INF = 1e9+7;
      
      int n;
      
      scanf("%d", &n);
      
      vector<int> arr(n);
      
      vector<vector<ll>> dp(n, vector<ll>(n, -1));
      
      vector<vector<int>> mids(n, vector<int>(n));
      
      vector<ll> pref_sums(n+1);
      
      ll pref_sum = 0;
      
      for (int i = 0; i < n; i++) {
          scanf("%d", &arr[i]);
          dp[i][i] = 0;
      }
      
      for (int i = 0; i <= n; i++) {
          pref_sum += arr[i];
          pref_sums[i] = pref_sum;
      }
      
      for (int length = 1; length < n; length++) {
          for (int left = 0; left+length < n; left++) {
              int right = left + length;
              //cout << left << " " << right << endl;
              for (int mid = left; mid < right; mid++) {
                  ll left_cost = dp[left][mid];
                  ll right_cost = dp[mid+1][right];
                  ll range_sum = pref_sums[right] - (left-1 < 0 ? 0 : pref_sums[left-1]);
                  ll my_cost = left_cost + right_cost + range_sum;
                  //cout << total << endl;
                  /*
                  if (total < dp[left][right]) {
                      // update chosen mid & min value
                      dp[left][right] = my_cost;//total;
                      //mids[left][right] = mid;
                  }
                  */
                  if (dp[left][right] == -1) {
                      dp[left][right] = my_cost;
                  }
                  else {
                      dp[left][right] = min(dp[left][right], my_cost);                
                  }
              }
          }
      }
      /*
      vector<pair<int, int>> v; // (start, end)
      
      v.push_back({0, n-1});
      
      ll ans = 0; //-dp[0][n-1]; // the last one 
      
      while (!v.empty()) {
          pair<int, int> cur = v.back();
          v.pop_back();
          if (cur.second - cur.first + 1 >= 2) { // interval at least two
              ans += dp[cur.first][cur.second];
              int mid = mids[cur.first][cur.second];
              cout << "L: " << cur.first << " R: " << cur.second << " Total: " << dp[cur.first][cur.second] << " mid: " << mid << endl;
              v.push_back({cur.first, mid});
              v.push_back({mid+1, cur.second});    
          }
      }
      */
      
      
  	/*
  	for (int i = 0; i < n; i++) {
  	    for (int j = 0; j < n; j++) {
  	        for (int mid = i; mid <= j; mid++) {
  	            ll cur = dp[i][mid];
  	            if (mid+1 <= j) {
  	                cur += dp[mid+1][j];
  	            }
  	            dp[i][j] = min(dp[i][j], cur);
  	        }
  	    }
  	}
  	*/
  	
  	//printf("%lld", ans);
  	
  	printf("%lld", dp[0][n-1]);
  	
  	return 0;
  }
  """
  
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**)"}]