我们都知道矩阵乘法：给定两个矩阵A和B，若A是n*r的矩阵，B是r*m的矩阵，则A*B的结果C是一个n*m的矩阵，且c[i,j]=∑a[i,k]*b[k,j]，其中1<=k<=r。很显然，求出每个C[i,j]的过程中，我们都做了r次标量乘法。因此，总的标量乘法次数是n*m*r。

矩阵乘法满足结合律。换句话说，即使乘的顺序不同，结果都是相同的。例如，四个矩阵<A1,A2,A3,A4>相乘，会有五种不同的顺序：

(A1(A2(A3A4)))

(A1((A2A3)A4))

((A1A2)(A3A4))

((A1(A2A3))A4)

(((A1A2)A3)A4)

但是，不同的顺序会导致不同的效率——本题中，我们希望将给定的矩阵乘起来，并且使得总的标量乘法次数最少。注意，本题中给定的矩阵可以看作是环形的——第一个和最后一个矩阵可以相乘！为了满足矩阵乘法的合法性，输入数据保证对于任意相邻的矩阵，它们相邻的维数一定相等。

【数据规模和约定】

n<=100

所有矩阵的行、列数都是不超过1000的正整数。

第一行一个整数n，表示矩阵个数。

接下来n行，每行两个整数，表示这个矩阵的行数和列数。

一个整数，表示最少乘法次数。