Time Limit:1000MS Memory Limit:65536K
Total Submit:5 Accepted:0
Description
两个矩阵A和B相乘的条件是A的列数等于B的行数。若A是一个i*k矩阵，B是一个k*j矩阵，则其乘积C=AB是一个i*j矩阵。我们知道要经过i*k*j次数乘得到C。
由于矩阵乘法满足结合律，在计算一个大于2个矩阵的乘法时有多种乘法策略。打个比方，X，Y和Z都是矩阵，我们要求XYZ。我们可以计算(XY)Z或者X(YZ).假如X是一个5*10的矩阵，Y是一个10*20的矩阵，Z是一个20*35的矩阵。我们来看下这两种不同的乘法，要经过多少次数乘得到要得到的矩阵。
(XY)Z
1. 5*20*10=1000次数乘，得到(XY)的乘积，它是一个5*20的矩阵。
2. 5*35*20=3500次数乘，得到最后要求的矩阵。
3. 总共用了4500次数乘。
X(YZ)
1. 10*35*20=7000次数乘，得到(YZ)的乘积，它是一个10*35的矩阵。
2. 5*35*10=1750次数乘，得到最后要求的矩阵。
3. 总共用了8750次数乘。
我们清楚地发现用(XY)Z能用较少的数乘得到最后结果。
现在，给你一串要乘得矩阵序列A1，A2,...,An.让你决定一种乘法策略得到A1A2...An相乘的结果，所使用的数乘的次数最少。
Input
第一行有一个正整数n(n<11)，表示有n个矩阵。接着有n行，每行有2个正整数(都不大于1000)，表示一个矩阵的行和列。这n行对应A1,A2,...,An.
有多组测试数据。
Output
对于每组测试数据，输出得到A1A2...An相乘结果，所使用最少的数乘的次数。
Sample Input
3
1 5
5 20
20 1
3
5 10
10 20
20 35
6
30 35
35 15
15 5
5 10
10 20
20 25
Sample Output
105
4500
15125
