import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the number of keys (n):");
        int n = sc.nextInt();
        double[] p = new double[n+1];
        double[] q = new double[n+1];
        
       System.out.println("Enter probabilities of successful searches for keys (p):");
        for(int i=1;i<=n;i++){
            p[i] = sc.nextDouble();
        }
        
       System.out.println("Enter probabilities of unsuccessful searches (q):");
        for(int i=0;i<=n;i++){
            q[i] = sc.nextDouble();
        }
        obst(p,q,n);
    }
    public static void obst(double[] p,double[] q,int n){
        double[][] w = new double[n+1][n+1];
        double[][] c = new double[n+1][n+1];
        int[][] r = new int[n+1][n+1];
        for(int i=0;i<=n;i++){
            w[i][i] = q[i];
            c[i][i] = 0;
            r[i][i] = 0;
        }
        for(int m = 1;m<=n;m++){
            for(int i=0;i<=n-m;i++){
                int j = i+m;
                w[i][j] = w[i][j-1] + p[j]+q[j];
                double mincost = Double.MAX_VALUE;
                int root = -1;
                for(int k=i+1;k<=j;k++){
                    double cost = c[i][k-1]+c[k][j]+w[i][j];
                    if(cost < mincost){
                        mincost = cost;
                        root = k;
                    }
                }
                c[i][j] = mincost;
                r[i][j] = root;
            }
        }
        System.out.println("Cost = "+c[0][n]);
        System.out.println("Weight = "+w[0][n]);
    }
}