import java.io.*;  
import java.util.*; 
class Optimal
{
public int p[]; 
public int q[]; 
public int a[]; 
public int w[][];
public int c[][];
public int r[][]; 
public int n;
int front,rear,queue[]; 
public Optimal(int SIZE)
{
p=new int[SIZE]; q= new int[SIZE]; a=new int[SIZE];
w=new int[SIZE][SIZE]; c=new int[SIZE][SIZE]; r=new int[SIZE][SIZE];
queue=new int[SIZE]; front=rear=-1;
}
/* This function returns a value in the range r[i][j-1] to r[i+1][j] SO that the cost c[i][k-1] + c[k][j] is minimum */
public int Min_Value(int i, int j)
{
int m,k=0;
int minimum = 32000;
for (m=r[i][j-1] ; m<=r[i+1][j] ; m++)
{
if ((c[i][m-1]+c[m][j]) < minimum)
{
minimum = c[i][m-1] + c[m][j]; k = m;
}
}
return k;
}
/* This function builds the table from all the given probabilities It basically computes C,r,W values */ 
public void OBST()
{
int i, j, k, l, m;
 
for (i=0 ; i<n ; i++)
 
{
// Initialize 
w[i][i] = q[i];
r[i][i] = c[i][i] = 0;
// Optimal trees with one node 
w[i][i+1] = q[i] + q[i+1] + p[i+1]; r[i][i+1] = i+1;
c[i][i+1] = q[i] + q[i+1] + p[i+1];
}
w[n][n] = q[n];
r[n][n] = c[n][n] = 0;
// Find optimal trees with m nodes 
for (m=2 ; m<=n ; m++)
{
for (i=0 ; i<=n-m ; i++)
{
j = i+m;
w[i][j] = w[i][j-1] + p[j] + q[j]; k = Min_Value(i,j);
c[i][j] = w[i][j] + c[i][k-1] + c[k][j]; r[i][j] = k;
}
}
}
/*This function builds the tree from the tables made by the OBST function */ 
public void build_tree()
{
int i, j, k;
System.out.print("The Optimal Binary Search Tree For The Given Nodes Is \n");
System.out.print("\n The Root of this OBST is :: "+r[0][n]);
System.out.print("\n The Cost Of this OBST is :: "+c[0][n]);
System.out.print("\n\n\tNODE\tLEFT CHILD\tRIGHT CHILD");
System.out.println("\n "); queue[++rear] = 0;
queue[++rear] = n; while(front != rear)
{
i = queue[++front]; j = queue[++front]; k = r[i][j];
System.out.print("\n "+k); if (r[i][k-1] != 0)
{
System.out.print(" "+r[i][k-1]); queue[++rear] = i; queue[++rear] = k-1;
}
else System.out.print(" -");
if(r[k][j] != 0)
{
System.out.print(" "+r[k][j]); queue[++rear] = k; queue[++rear] = j;
}
else
System.out.print(" -");
}
System.out.println("\n");
}
}
/* This is the main function */ 
class OBSTDemo
{
public static void main (String[] args ) throws IOException,NullPointerException
{
Optimal obj=new Optimal(10); int i;
System.out.print("\n Optimal Binary Search Tree \n"); 
System.out.print("\n Enter the number of nodes");
obj.n=getInt();
System.out.print("\n Enter the data as \n");
for (i=1;i<=obj.n;i++)
{
System.out.print("\n a["+i+"]"); obj.a[i]=getInt();
}
for (i=1 ; i<=obj.n ; i++)
{
System.out.println("p["+i+"]"); obj.p[i]=getInt();
}
for (i=0 ; i<=obj.n ; i++)
{
System.out.print("q["+i+"]"); obj.q[i]=getInt();
} obj.OBST();
obj.build_tree();
}
public static String getString() throws IOException
{
InputStreamReader input = new InputStreamReader(System.in);
BufferedReader b = new BufferedReader(input);
String str = b.readLine();//reading the string from console
return str;
}
public static char getChar() throws IOException
{
String str = getString();
return str.charAt(0);//reading first char of console string
}
public static int getInt() throws IOException
{
String str = getString();
return Integer.parseInt(str);//converting console string to numeric value
}

aW1wb3J0IGphdmEuaW8uKjsgIAppbXBvcnQgamF2YS51dGlsLio7IApjbGFzcyBPcHRpbWFsCnsKcHVibGljIGludCBwW107IApwdWJsaWMgaW50IHFbXTsgCnB1YmxpYyBpbnQgYVtdOyAKcHVibGljIGludCB3W11bXTsKcHVibGljIGludCBjW11bXTsKcHVibGljIGludCByW11bXTsgCnB1YmxpYyBpbnQgbjsKaW50IGZyb250LHJlYXIscXVldWVbXTsgCnB1YmxpYyBPcHRpbWFsKGludCBTSVpFKQp7CnA9bmV3IGludFtTSVpFXTsgcT0gbmV3IGludFtTSVpFXTsgYT1uZXcgaW50W1NJWkVdOwp3PW5ldyBpbnRbU0laRV1bU0laRV07IGM9bmV3IGludFtTSVpFXVtTSVpFXTsgcj1uZXcgaW50W1NJWkVdW1NJWkVdOwpxdWV1ZT1uZXcgaW50W1NJWkVdOyBmcm9udD1yZWFyPS0xOwp9Ci8qIFRoaXMgZnVuY3Rpb24gcmV0dXJucyBhIHZhbHVlIGluIHRoZSByYW5nZSByW2ldW2otMV0gdG8gcltpKzFdW2pdIFNPIHRoYXQgdGhlIGNvc3QgY1tpXVtrLTFdICsgY1trXVtqXSBpcyBtaW5pbXVtICovCnB1YmxpYyBpbnQgTWluX1ZhbHVlKGludCBpLCBpbnQgaikKewppbnQgbSxrPTA7CmludCBtaW5pbXVtID0gMzIwMDA7CmZvciAobT1yW2ldW2otMV0gOyBtPD1yW2krMV1bal0gOyBtKyspCnsKaWYgKChjW2ldW20tMV0rY1ttXVtqXSkgPCBtaW5pbXVtKQp7Cm1pbmltdW0gPSBjW2ldW20tMV0gKyBjW21dW2pdOyBrID0gbTsKfQp9CnJldHVybiBrOwp9Ci8qIFRoaXMgZnVuY3Rpb24gYnVpbGRzIHRoZSB0YWJsZSBmcm9tIGFsbCB0aGUgZ2l2ZW4gcHJvYmFiaWxpdGllcyBJdCBiYXNpY2FsbHkgY29tcHV0ZXMgQyxyLFcgdmFsdWVzICovIApwdWJsaWMgdm9pZCBPQlNUKCkKewppbnQgaSwgaiwgaywgbCwgbTsKCmZvciAoaT0wIDsgaTxuIDsgaSsrKQoKewovLyBJbml0aWFsaXplIAp3W2ldW2ldID0gcVtpXTsKcltpXVtpXSA9IGNbaV1baV0gPSAwOwovLyBPcHRpbWFsIHRyZWVzIHdpdGggb25lIG5vZGUgCndbaV1baSsxXSA9IHFbaV0gKyBxW2krMV0gKyBwW2krMV07IHJbaV1baSsxXSA9IGkrMTsKY1tpXVtpKzFdID0gcVtpXSArIHFbaSsxXSArIHBbaSsxXTsKfQp3W25dW25dID0gcVtuXTsKcltuXVtuXSA9IGNbbl1bbl0gPSAwOwovLyBGaW5kIG9wdGltYWwgdHJlZXMgd2l0aCBtIG5vZGVzIApmb3IgKG09MiA7IG08PW4gOyBtKyspCnsKZm9yIChpPTAgOyBpPD1uLW0gOyBpKyspCnsKaiA9IGkrbTsKd1tpXVtqXSA9IHdbaV1bai0xXSArIHBbal0gKyBxW2pdOyBrID0gTWluX1ZhbHVlKGksaik7CmNbaV1bal0gPSB3W2ldW2pdICsgY1tpXVtrLTFdICsgY1trXVtqXTsgcltpXVtqXSA9IGs7Cn0KfQp9Ci8qVGhpcyBmdW5jdGlvbiBidWlsZHMgdGhlIHRyZWUgZnJvbSB0aGUgdGFibGVzIG1hZGUgYnkgdGhlIE9CU1QgZnVuY3Rpb24gKi8gCnB1YmxpYyB2b2lkIGJ1aWxkX3RyZWUoKQp7CmludCBpLCBqLCBrOwpTeXN0ZW0ub3V0LnByaW50KCJUaGUgT3B0aW1hbCBCaW5hcnkgU2VhcmNoIFRyZWUgRm9yIFRoZSBHaXZlbiBOb2RlcyBJcyBcbiIpOwpTeXN0ZW0ub3V0LnByaW50KCJcbiBUaGUgUm9vdCBvZiB0aGlzIE9CU1QgaXMgOjogIityWzBdW25dKTsKU3lzdGVtLm91dC5wcmludCgiXG4gVGhlIENvc3QgT2YgdGhpcyBPQlNUIGlzIDo6ICIrY1swXVtuXSk7ClN5c3RlbS5vdXQucHJpbnQoIlxuXG5cdE5PREVcdExFRlQgQ0hJTERcdFJJR0hUIENISUxEIik7ClN5c3RlbS5vdXQucHJpbnRsbigiXG4gIik7IHF1ZXVlWysrcmVhcl0gPSAwOwpxdWV1ZVsrK3JlYXJdID0gbjsgd2hpbGUoZnJvbnQgIT0gcmVhcikKewppID0gcXVldWVbKytmcm9udF07IGogPSBxdWV1ZVsrK2Zyb250XTsgayA9IHJbaV1bal07ClN5c3RlbS5vdXQucHJpbnQoIlxuICIrayk7IGlmIChyW2ldW2stMV0gIT0gMCkKewpTeXN0ZW0ub3V0LnByaW50KCIgIityW2ldW2stMV0pOyBxdWV1ZVsrK3JlYXJdID0gaTsgcXVldWVbKytyZWFyXSA9IGstMTsKfQplbHNlIFN5c3RlbS5vdXQucHJpbnQoIiAtIik7CmlmKHJba11bal0gIT0gMCkKewpTeXN0ZW0ub3V0LnByaW50KCIgIityW2tdW2pdKTsgcXVldWVbKytyZWFyXSA9IGs7IHF1ZXVlWysrcmVhcl0gPSBqOwp9CmVsc2UKU3lzdGVtLm91dC5wcmludCgiIC0iKTsKfQpTeXN0ZW0ub3V0LnByaW50bG4oIlxuIik7Cn0KfQovKiBUaGlzIGlzIHRoZSBtYWluIGZ1bmN0aW9uICovIApjbGFzcyBPQlNURGVtbwp7CnB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzICkgdGhyb3dzIElPRXhjZXB0aW9uLE51bGxQb2ludGVyRXhjZXB0aW9uCnsKT3B0aW1hbCBvYmo9bmV3IE9wdGltYWwoMTApOyBpbnQgaTsKU3lzdGVtLm91dC5wcmludCgiXG4gT3B0aW1hbCBCaW5hcnkgU2VhcmNoIFRyZWUgXG4iKTsgClN5c3RlbS5vdXQucHJpbnQoIlxuIEVudGVyIHRoZSBudW1iZXIgb2Ygbm9kZXMiKTsKb2JqLm49Z2V0SW50KCk7ClN5c3RlbS5vdXQucHJpbnQoIlxuIEVudGVyIHRoZSBkYXRhIGFzIFxuIik7CmZvciAoaT0xO2k8PW9iai5uO2krKykKewpTeXN0ZW0ub3V0LnByaW50KCJcbiBhWyIraSsiXSIpOyBvYmouYVtpXT1nZXRJbnQoKTsKfQpmb3IgKGk9MSA7IGk8PW9iai5uIDsgaSsrKQp7ClN5c3RlbS5vdXQucHJpbnRsbigicFsiK2krIl0iKTsgb2JqLnBbaV09Z2V0SW50KCk7Cn0KZm9yIChpPTAgOyBpPD1vYmoubiA7IGkrKykKewpTeXN0ZW0ub3V0LnByaW50KCJxWyIraSsiXSIpOyBvYmoucVtpXT1nZXRJbnQoKTsKfSBvYmouT0JTVCgpOwpvYmouYnVpbGRfdHJlZSgpOwp9CnB1YmxpYyBzdGF0aWMgU3RyaW5nIGdldFN0cmluZygpIHRocm93cyBJT0V4Y2VwdGlvbgp7CklucHV0U3RyZWFtUmVhZGVyIGlucHV0ID0gbmV3IElucHV0U3RyZWFtUmVhZGVyKFN5c3RlbS5pbik7CkJ1ZmZlcmVkUmVhZGVyIGIgPSBuZXcgQnVmZmVyZWRSZWFkZXIoaW5wdXQpOwpTdHJpbmcgc3RyID0gYi5yZWFkTGluZSgpOy8vcmVhZGluZyB0aGUgc3RyaW5nIGZyb20gY29uc29sZQpyZXR1cm4gc3RyOwp9CnB1YmxpYyBzdGF0aWMgY2hhciBnZXRDaGFyKCkgdGhyb3dzIElPRXhjZXB0aW9uCnsKU3RyaW5nIHN0ciA9IGdldFN0cmluZygpOwpyZXR1cm4gc3RyLmNoYXJBdCgwKTsvL3JlYWRpbmcgZmlyc3QgY2hhciBvZiBjb25zb2xlIHN0cmluZwp9CnB1YmxpYyBzdGF0aWMgaW50IGdldEludCgpIHRocm93cyBJT0V4Y2VwdGlvbgp7ClN0cmluZyBzdHIgPSBnZXRTdHJpbmcoKTsKcmV0dXJuIEludGVnZXIucGFyc2VJbnQoc3RyKTsvL2NvbnZlcnRpbmcgY29uc29sZSBzdHJpbmcgdG8gbnVtZXJpYyB2YWx1ZQp9