URI Online Judge | 1976

Matrices

By Gabriel Duarte, UNIFESO BR Brazil

Timelimit: 3

Gustavo in one of his pre-calculus classes learned to do multiplication of matrices, as he is a very smart student, quickly he realized that when we do the multiplication, the order in which the matrices are multiplied can influence the total amount of necessary accounts for find the answer.

Although very dedicated, Gustavo is with little time to do college work, as is currently studying hard for programming contest, so he asked for his help on a task requested in pre-calculation classes.
The teacher gave various matrices for the class to train multiplication, then Gustavo need a program that given the dimensions of the matrices, the program have to report on the best order to carry out the multiplications taking into account the least amount of necessary accounts to generate reply.

How you are Gustavo friend's and has more time than he, decided to help him, but with some rules:
1st Gustavo always have to inform matrices where the multiplication in the order given is always possible;
2nd If there is more than a great solution, your program will only report the amount of necessary accounts for multiplication.

Input

The input contains several test cases. The first line of each test case contains an integer N (1 ≤ N ≤ 1000), indicating the number of matrices to be multiplied. It follows then N rows each containing two integers L and C (1 ≤ L, C ≤ 100) indicating the number of rows and columns of each array. The entry ends when N = 0 and should not be processed.

Output

Assume that the matrices names are A1, A2, ..., AN. For each test case, your program should print a line containing the order of the matrices to be multiplied (following the example output), in case of more than one possible solution your program should print only the total amount of necessary accounts.

Input Sample Output Sample

6
30 35
35 15
15 5
5 10
10 20
20 25
3
5 5
5 5
5 5
0

((A1(A2A3))((A4A5)A6))
250