在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×q的矩阵,B是一个q×r的矩阵,则其乘积C=AB是一个p×r的矩阵。计算C=AB总共需要p×q×r次乘法。 现在的问题是,给定n个矩阵{A1,A2,...,An}。其中Ai与Ai+1是可乘的,i=1,2,...,n-1。 要求计算出这n个矩阵的连乘积A1A2...An最少需要多少次乘法。 输入 输入数据的第一行是一个整树n(0 < n ≤ 10),表示矩阵的个数。 接下来的n行每行两个整数p,q( 0 < p,q < 100),分别表示一个矩阵的行数和列数。 输出 输出一个整数:计算连乘积最少