#include <iostream>
#include <algorithm>
#include <string>
#include <iostream> #define INF 0xfffffff
using namespace std;
const int maxn = + ;
int a[maxn];
int sum[maxn];
int dp[maxn][maxn];
//dp[i][j] 从i到j所需的最少 int main(){
ios::sync_with_stdio(false);
/*
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
*/
int n;
cin >> n;
for (int i = ; i <= n; i++){
cin >> a[i];
sum[i] = sum[i - ] + a[i];
}
//init for (int l = ; l <= n; l++){
//中间的长度
for (int sta = ; sta <= n - l + ; sta++){
int endd = sta + l - ;
int Min = INF;
for (int k = sta; k < endd; k++){
if (dp[sta][k] + dp[k + ][endd] + sum[endd] - sum[sta - ] < Min){
Min = dp[sta][k] + dp[k + ][endd] + sum[endd] - sum[sta - ];
}
}
dp[sta][endd] = Min;
}
}
cout << dp[][n] << endl; //fclose(stdin);
//fclose(stdout);
system("pause");
return ;
}