该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述：

给定N个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少?矩阵的行r[i]和列c[i]的范围：1<=r[i],c[i]<=100

输入格式：

第一行有一个正整数N，1≤N≤100 接下来有N行，每行两个正整数，表示矩阵的行数和列数 保证本行的列数c[i]等于下一行的行数r[i+1]

输出格式：

所需的最少乘法次数

样例：

3
10 100
100 5
5 50

7500

提示