pid=737" method="post" enctype="application/x-www-form-urlencoded" style="margin:0px; padding:0px">

#include <stdio.h>

#include<cstring>

#include<algorithm>

#define M 205

#define limit 214748647

int cut[M],n,dp[M][M],sum[M];

int d(int i,int j)

{

    if(dp[i][j])return dp[i][j];

    if(i==j-1)return dp[i][j]=cut[i]+cut[j];

    if(i==j)return 0;

    else

    {

        dp[i][j]=limit;

        for(int k=i;k<j;k++)

        {

            int t=d(i,k)+d(k+1,j)+sum[j]-sum[i-1];

            if(t<dp[i][j])dp[i][j]=t;

        }

    }

    return dp[i][j];

}

int main()

{

    //freopen("input.txt","r",stdin);

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

    {

        memset(sum,0,sizeof(sum));

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

            scanf("%d",cut+i);

            sum[i]+=sum[i-1]+cut[i];

        }

        memset(dp,0,sizeof(dp));

        int ans=d(1,n);

        printf("%d\n",ans);

    }

    return 0;

}