题目描述

墨老师:"其实大家要学会学习,而不只是死记硬背,例如爱恩斯坦曾经说过:‘我从来 不记在辞典上已经印着的东西,我的记忆力是用来记忆书本上没有的东西。"

楚继光如释重负:"老师，我明白了,接下来你要讲的矩阵乘法,我终于可以不记了。"

墨老师:"呃,这个知识点,你还是要记的。"

矩阵乘法是线性代数中最基础的一个知识点.设矩阵$\red{A}$为一个$\red{n}$行$\red{m}$列的矩阵,矩阵 $\red{B}$为$\red{x}$行$\red{y}$列,那么$\red{A}$能乘$\red{B}$的条件为$\red{m=x,}$它们相乘将得出一个$\red{n}$行$\red{y}$列的矩阵,进行 一次矩阵乘法的运算次数为$\red{n\times m\times y,}$现在给出$\red{k}$个矩阵，你每次可以合并相邻的两个矩 阵,将它们做乘法得出的矩阵作为合并的结果,请问如何合并能使得总的运算次数最少。

输入格式

第一行一个数$\red{k(k≤}$$\red{100).}$ 接下来$\red{k}$行,每行两个正整数表示该矩阵的行和列$\red{(}$每个数$\red{≤}$$\red{50).}$

输出格式

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

样例

输入样例

3
1 5
5 20
20 1

输出样例

105