import java.util.*;


public class SkewTree extends Object {

    static public void compute(int[] probs){
        int n = probs.length;

        int[][] costs = new int[n][n];
        int[][] roots = new int[n][n];
        int[][] sums = new int[n][n];

        for(int i = 0; i < n; i++){
            costs[i][i] = probs[i];
            sums[i][i] = probs[i];
        }

        int cst = 0;
        
        for(int k = 1; k < n; k++){
            for(int i = 0; i < n - k; i++){
                int j = i + k;

                costs[i][j] = Integer.MAX_VALUE;
                sums[i][j] = probs[i] + sums[i + 1][j];

                for(int h = i + 1; h < j; h++){
                    cst = probs[h] + sums[i][h - 1] +
                        sums[h + 1][j] + costs[i][h - 1] + costs[h + 1][j];

                    if(cst < costs[i][j]){
                        costs[i][j] = cst;
                        roots[i][j] = h;
                    }
                }

                // bordercase h = i
                cst = probs[i] + sums[i + 1][j] + costs[i + 1][j];

                if(cst < costs[i][j]){
                    costs[i][j] = cst;
                    roots[i][j] = i;
                }

                // bordercase h = j
                cst = probs[j] + sums[i][j - 1] + costs[i][j - 1];

                if(cst < costs[i][j]){
                    costs[i][j] = cst;
                    roots[i][j] = j;
                }
            }
        }

        int result = Integer.MAX_VALUE;
        int root = -1;

        for(int h = 1; h < n - 1; h++){
            cst = probs[h] + sums[0][h - 1] + sums[h + 1][n - 1] +
                costs[0][h - 1] + costs[h + 1][n - 1];
            
            if(cst < result){
                result = cst;
                root = h;
            }
        }

        // bordercase 0
        cst = probs[0] + sums[1][n - 1] + costs[1][n - 1];
        
        if(cst < result){
            result = cst;
            root = 0;
        }
        
        // bordercase n - 1
        cst = probs[n - 1] + sums[0][n - 2] + costs[0][n - 2];
        
        if(cst < result){
            result = cst;
            root = n - 1;
        }
        

        System.out.println("root = " + root);
        System.out.println("cost = " + result);

    }


    static public void main(String[] args){

        int[] input = new int[2];

        input[0] = 1;
        input[1] = 2;

        SkewTree.compute(input);

        input = new int[6];

        input[0] = 1;
        input[1] = 2;
        input[2] = 4;
        input[3] = 3;
        input[4] = 5;
        input[5] = 6;

        SkewTree.compute(input);


        input = new int[6];

        input[0] = 49;
        input[1] = 13;
        input[2] = 65;
        input[3] = 62;
        input[4] = 16;
        input[5] = 34;

        SkewTree.compute(input);
        
    }

}