連鎖行列積

$n$ 個の行列の連鎖 $M_1, M_2, M_3,...,M_n$ が与えられたとき、スカラー乗算の回数が最小になるように積 $M_1M_2M_3...M_n$ の計算順序を決定する問題を連鎖行列積問題(Matrix-Chain Multiplication problem)と言います。

$n$ 個の行列について、行列 $M_i$ の次元が与えられたとき、積 $M_1M_2...M_n$ の計算に必要なスカラー乗算の最小の回数を求めるプログラムを作成してください。

入力

入力の最初の行に、行列の数 $n$ が与えられます。続く $n$ 行で行列 $M_i (i = 1...n)$ の次元が空白区切りの２つの整数 $r$、$c$ で与えられます。$r$ は行列の行の数、$c$ は行列の列の数を表します。

出力

最小の回数を１行に出力してください。

制約

• $1 \leq n \leq 100$
• $1 \leq r, c \leq 100$

入力例 1

6
30 35
35 15
15 5
5 10
10 20
20 25

出力例 1

15125

---