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

【题意】

研究两个矩阵相乘，用到乘法的次数是多少。所以一个矩阵的说明，只需要给出行数和列数。

两个矩阵相乘，用到乘法的次数是一定的，比如 矩阵1 $(r_1,c_1)$（说明：$r_1$ 是 矩阵1 的行数，$c_1$ 是 矩阵1 的列数）和 矩阵2 $(r_2,c_2)$， 矩阵1 × 矩阵2 用到的乘法次数就是 $r_1*c_2 * c_1$ 或者 $r_1*c_2 * r_2$ 。

$r_1*c_2 * c_1$ 和 $r_1*c_2 * r_2$ 一样吗？ 一样的。 因为 $c_1=r_2$ 。 为什么？ 因为不满足 $c_1=r_2$ 的两个矩阵无法相乘。

拓展：矩阵相乘满足交换律吗？

【输入格式】

第一行一个整数 $n( 1 \le n \le 500)$，代表 $n$ 个矩阵。

第二行至第 $n+1$ 行，每行两个数 $r_i，c_i ( 1 \le r_i,c_i \le 10 )$ 代表第 $i$ 个矩阵的行数和列数 。

【输出格式】

输出最少乘运算次数 。

【样例输入】

3 
3 5 
5 6 
6 2 

【样例输出】

90 

【样例解释】

方案一：第一个矩阵和第二个矩阵结合 变成矩阵（3 6）同时用了 3×5×6=90 次乘法，然后矩阵（3 ， 6 ）和第三个矩阵（6 ，2）结合，变成（3，2）又用 3×6×2=36次，总共用了 126 次

方案二：第二个矩阵和第三个矩阵结合 变成矩阵（5 2）同时用了 5×6×2=60次乘法，然后第一个矩阵（3 ， 5）和矩阵（5 ， 2 ）结合，变成（3，2）又用 3×5×2=30 次，总共用了 90 次

结论：采用方案二。

解法：先处理相邻两个，然后计算相邻三个～～，直到相邻 $n$个就是答案。如果 $1 \le r_i,c_i \le 10^9$ ，那么就要用到高精度了。