import java.util.Scanner;

public class OptimalBSTUserInput {

    // Function to construct and return the cost of the optimal BST
    public static int optimalBST(int[] keys, int[] freq, int n) {
        int[][] cost = new int[n][n];

        // Base case: cost when the tree contains only one key
        for (int i = 0; i < n; i++) {
            cost[i][i] = freq[i];
        }

        // Compute the cost for chains of length 2 to n
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                cost[i][j] = Integer.MAX_VALUE;

                // Try making each key in keys[i...j] the root
                for (int r = i; r <= j; r++) {
                    int leftCost = (r > i) ? cost[i][r - 1] : 0;
                    int rightCost = (r < j) ? cost[r + 1][j] : 0;
                    int rootCost = leftCost + rightCost + sum(freq, i, j);

                    if (rootCost < cost[i][j]) {
                        cost[i][j] = rootCost;
                    }
                }
            }
        }
        return cost[0][n - 1];
    }

    // Utility function to calculate the sum of frequencies from i to j
    private static int sum(int[] freq, int i, int j) {
        int total = 0;
        for (int k = i; k <= j; k++) {
            total += freq[k];
        }
        return total;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Input the number of keys
        System.out.print("Enter the number of keys: ");
        int n = scanner.nextInt();

        // Input keys
        int[] keys = new int[n];
        System.out.println("Enter the keys in sorted order:");
        for (int i = 0; i < n; i++) {
            keys[i] = scanner.nextInt();
        }

        // Input frequencies
        int[] freq = new int[n];
        System.out.println("Enter the frequencies of the keys:");
        for (int i = 0; i < n; i++) {
            freq[i] = scanner.nextInt();
        }

        // Calculate and print the cost of the optimal BST
        int cost = optimalBST(keys, freq, n);
        System.out.println("Cost of Optimal BST: " + cost);

        scanner.close();
    }
}