#include<iostream>

 #include<cstdio>

 using namespace std;

 const int N=;

 const int INF=0x7fffffff;

 int n;

 int a[N],sum[N],dp[N][N],s[N][N];

 void f()

 {    for (int i=;i<=n;i++) dp[i][i]=,s[i][i]=i;

      for (int r=;r<n;r++)

      {

          for (int i=;i<n;i++)

         {

             int j=i+r;

             if(j>n) break;

             dp[i][j]=INF;

             for (int k=s[i][j-];k<=s[i+][j];k++)

             {

                 if(dp[i][j]>dp[i][k]+dp[k+][j])

                 {

                     dp[i][j]=dp[i][k]+dp[k+][j];

                     s[i][j]=k;

                 }

             }

             dp[i][j]+=sum[j]-sum[i-];

         }

     }

 }

 int main()

 {

      while(~scanf("%d",&n))

      {

          sum[]=;

         for (int i=;i<=n;i++)

         {

             scanf("%d",&a[i]);

             sum[i]=sum[i-]+a[i];

         }

         f();

         printf("%d\n",dp[][n]);

      }

      return ;

 }