题目描述

给定 n个矩阵{A1,A2,...,An}，考察这 n个矩阵的连乘积 A1A2...An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。
矩阵连乘积的计算次序与其计算量有密切关系。例如，考察计算 3 个矩阵{A1,A2,A3}连乘积的例子。 设这3个矩阵的维数分别为$10*100， 100*5，和5*50$。

若按(A1A2)A3 计算，3 个矩阵连乘积需要的数乘次数为 $10*100*5+10*5*50 = 7500$。

若按 A1(A2A3)计算，则总共需要$100*5*50+10*100*50 = 75000 $次数乘。

现在你的任务是给出一个矩阵连乘式，计算其需要的最少乘法次数。

输入格式

第一行是一个整数n (1≤n≤100)，表示矩阵的个数。 接下来 n 行，每行两个整数 a,b，分别表示该矩阵的行数和列数，其中1<a,b<100。

输出格式

输出仅一行包含一个整数，即将该矩阵连乘方案需要的最少乘法次数。

样例数据

input

3 
10 100 
100 5 
5 50

output

7500

数据规模与约定

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$