/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2009 by Doina Logofatu
************************************************/

import java.io.*;
import java.util.*;

public class P12MatrixSequenceMultiplication {
  private static final String FileInputName = "matrix.in";
  private static final String FileOutputName = "matrix.out";

  private int d[];
  private int op[], cl[];
  private long c[][];

  P12MatrixSequenceMultiplication(int[] d) {
    this.d = d;
    int szD = d.length;
    this.op = new int[szD];
    this.cl = new int[szD];
    this.c = new long[szD][szD];
  }

  void doProcess() {
    int n = d.length - 1;
    int i, j, k, p;

    for (j = 0; j < n; j++) {
      for (i = 0; i < j; i++)
        c[i][j] = Long.MAX_VALUE;
      c[j][j] = 0;
    }
    for (p = 1; p < n; p++)
      for (i = 0, j = p; j < n; i++, j++)
        for (k = i; k < j; k++) {
          long aux = 
             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;
          }
        }
  }

  private void constructOrder(int i, int j) {
    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(i, k);
      constructOrder(k + 1, j);
    }
  }

  void write(PrintStream out) {
    int n = d.length - 1;
    out.printf("minimal = %d%n", c[0][n - 1]);
    constructOrder(0, n - 1);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < op[i]; j++)
        out.print('(');
      out.print('A');
      out.print(i);
      for (int j = 0; j < cl[i]; j++)
        out.print(')');
    }
  }

  public static void main(String[] args) throws IOException {
    Scanner scanner = null;
    PrintStream out = null;
    try {
      scanner = new Scanner(new File(FileInputName));

      List<Integer> list = new ArrayList<Integer>();
      while (scanner.hasNextInt()) {
        int i = scanner.nextInt();
        int j = scanner.nextInt();

        int szD = list.size();
        if (szD == 0) {
          list.add(i);
        } else if (list.get(szD - 1).intValue() != i) {
          throw new IOException("Ungueltige Eigabedaten!");
        }
        list.add(j);
      }

      int arr[] = new int[list.size()];
      for (int k = 0; k < list.size(); k++)
        arr[k] = list.get(k);
      P12MatrixSequenceMultiplication p = new P12MatrixSequenceMultiplication(
          arr);
      p.doProcess();
      out = new PrintStream(new File(FileOutputName));
      p.write(out);

    } finally {
      if (scanner != null) {
        scanner.close();
      }
      if (out != null) {
        out.close();
      }
    }
  }
}