import java.io.*;
import java.util.Arrays;

class Main {
    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader in = new BufferedReader(isr);
        String[] strs = in.readLine().split(" ");
        int N = Integer.parseInt(strs[0]);
        strs = in.readLine().split(" ");
        int[] a = new int[N+1];
        int[] s = new int[N+1];
        for (int i = 1; i <= N; i++) {
            a[i] = Integer.parseInt(strs[i - 1]);
            s[i] = s[i - 1] + a[i];
        }
        in.close();
        isr.close();

        OutputStreamWriter osw = new OutputStreamWriter(System.out);
        BufferedWriter out = new BufferedWriter(osw);

        int[][] f = new int[N+1][N+1];
        for (int i = 1; i <= N; i++) Arrays.fill(f[i], Integer.MAX_VALUE);
        for (int i = 1; i <= N; i++) f[i][i] = 0;
        //关键：按照区间长度递增进行循环，才能遍历到所有区间合并消耗的体力
        for (int len = 1; len <= N; len++)
            for (int i = 1; i <= N - len; i++) {
                int l = i, r = i + len;
                for (int k = 0; k <= r - l  - 1; k++)
                    f[l][r] = Math.min(f[l][r], f[l][l + k] + f[l + k + 1][r] + s[r] - s[l - 1]);
                //System.out.println(String.format("f[%d][%d] : %d",l,r,f[l][r]));
            }
        out.write(f[1][N]+"");        


        out.flush();
        out.close();
        osw.close();
    }
}