/************************************************
Algorithmen und Problemloesungen mit C++,
http://www.algorithmen-und-problemloesungen.de
Copyright @2006-2007, Doina Logofatu
************************************************/

#include <fstream>
#include <vector>

using namespace std;

void read(ifstream &in, ofstream& out, vector<unsigned>& d){
  int i, j; 
  while(in && !in.eof()){
    if(in >> i >> j){
      if(d.size()>0 && d[d.size()-1]!=i){
        out << "Wrong input data: ";
        exit(1);
      } 
      if(d.size()==0){d.push_back(i); d.push_back(j);}
      else{
        d.push_back(j);
      }      
    }
  }
}

void doProcess(vector<unsigned> &d, 
               unsigned long long C[][101]){

  int n = (int) (d.size()-1);
  int i, j, k, p, aux;
  for(i=0; i<n; i++) C[i][i]=0;
  for(i=0; i<n-1; i++) C[i][i+1]=d[i]*d[i+1]*d[i+2];
  for(p=2; p<n; p++){
    for(i=0; i<n-p; i++){
      j=i+p;
      C[i][j]=C[i][i]+C[i+1][j]+d[i]*d[i+1]*d[j+1];
      C[j][i]=i;
      for(k=i+1; k<j; k++){
        aux = (int) (C[i][k]+C[k+1][j]+d[i]*d[k+1]*d[j+1]);
        if(C[i][j]>aux){C[i][j]=aux; C[j][i]=k;}
      }
    }
  }
}

void constructOrder(unsigned long long C[][101], 
  int i, int j, short op[100], 
  short cl[100]){
  if((j-i)>1){
    int k=(int)C[j][i];
    if(i!=k){
      op[i]++; cl[k]++;
    }
    if(k+1!=j) { 
      op[k+1]++; cl[j]++;
    }
    constructOrder(C, i, k, op, cl);
    constructOrder(C, k+1, j, op, cl);
  }
}

int main(){
  ifstream in("matrix.in");
  ofstream out("matrix.out");
  int  n, i, j;
  vector<unsigned> d;
  unsigned long long C[101][101];
  short op[100], cl[100];
  read(in, out, d);
  n=(int)(d.size()-1);
  for(i=0; i<n; i++){
    op[i]=0;
    cl[i]=0;
  }
  doProcess(d, C);
  out << "minimal = " << C[0][n-1] << endl; 
  constructOrder(C, 0, n-1, op, cl);
  for(i=0; i<n; i++){
    for(j=0; j<op[i]; j++) out<<"(";
    out << "A" << i;
    for(j=0; j<cl[i]; j++) out<<")";
  }
  return 0;
}