内存限制：128 MB
时间限制：1.000 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：1
通过：1
给定 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。
对于每组数据，输出仅一行包含一个整数，即将该矩阵连乘方案需要的最少乘法次数。