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

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

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

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

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

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