测试数据来自 system/1178

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　在科学计算中经常要计算矩阵的乘积。矩阵 \(A\) 和 \(B\) 可乘的条件是矩阵 \(A\) 的列数等于矩阵 \(B\) 的行数。若 \(A\) 是一个 \(m\) 行、\(n\) 列的矩阵（简称 \(m×n\) 的矩阵），\(B\) 是一个 \(n\) 行、\(p\) 列的矩阵（简称 \(n×p\) 的矩阵），则其乘积 \(C=A×B\) 是一个 \(m×p\) 的矩阵。其标准计算公式为：
　　　　　　　　
　　由该公式知计算 \(C=A×B\) 总共需要进行 \(m×n×p\) 次的数乘法，我们将两个矩阵乘法次数定义为矩阵相互乘的时间复杂度。
　　矩阵乘法满足矩阵乘法满足结合律（但不满足交换律），即对于 \(D=A×B×C\)，可以有如下两种计算方式：
　　　\(1、D=(A×B)×C\)　　
　　　\(2、D=A×(B×C)\)
　　假设 \(A\) 是个 \(10×100\) 的矩阵、\(B\) 是个 \(100×5\) 的矩阵，\(C\) 是个 \(5×50\) 的矩阵，那么：
　　　●按照第一种计算方法得到的时间复杂度是：\(10×100×5+10×5×50=7500\)；
　　　●按照第一种计算方法得到的时间复杂度是：\(100×5×50+10×100×50=75000\)；
　　所以不同的计算顺序得到的时间复杂度是不一样的，现在的问题是：顺序给出n个矩阵的大小，请计算出它们的乘积的最小的时间复杂度。

【输入格式】

　　第一行输入一个正整数 \(n\)，表示有 \(n\)个矩阵。接下来 \(n\) 行每行两个正整数 \(X_i，Y_i\)，其中第 \(i\) 行的两个数表示第 \(i\) 个矩阵的规模为 \(X_i\) 行、\(Y_i\) 列。所有的 \(X_i,Y_i<=100\)。

【输出格式】

　　\(n\) 个矩阵连乘最小时间复杂度。

【输入输出样例】

　Input

3
10 100
100 5
5 50

　Output

7500

【数据限制】

　　\(2<=n<=100\)

【来源】

　　Mr.he