306015 - 矩阵连乘

矩阵乘法是线性代数中最基础的一个知识点，矩阵相乘只有在第一个矩阵的列数和第二个矩阵的行数相同时才有定义。假如A为m×n矩阵，B为n×p矩阵，则A乘B(有时记做A•B)会是一个m×p矩阵。

设矩阵A为一个n行m列的矩阵，矩阵B为x行y列，那么A能乘B的条件为m＝x，它们相乘将得出一个n行y列的矩阵，进行一次矩阵乘法的运算次数为n×m×y。

例如一个3×2的矩阵与一个2×3的矩阵的相乘会是一个2×2的矩阵，例如：

　　现在来看一个例子：A_1，A_2，A_3分别是10×100,100×5和5×50的矩阵。如果按照((A_1A_2)A_3)来计算，则计算所需的乘法次数是10×100×5＋10×5×50＝7500。如果按照(A_1(A_2A_3))来计算，则需要的乘法次数是100×5×50＋10×100×50＝75000，整整是前者的10倍。由此可见，在计算矩阵连乘积时，不同的加括号方式所导致的不同的计算对计算量有很大的影响。如何确定计算矩阵连乘积A_1A_2，…，A_n的一个计算次序，使得依此次序计算矩阵连乘积需要的乘法次数最少便成为一个问题。

现在给出k个矩阵，你每次可以合并相邻的两个矩阵，将它们做乘法得出的矩阵作为合并的结果，请问如何合并能使得总的运算次数最少。

第一行一个数k（k\le100）。

接下来k行，每行两个正整数表示该矩阵的行和列（每个数\le50）。

一个整数表示最少的合并代价。