Optimization on matrices multiplication

Description

In data science, the features can be represented in Matrix format, so it’s common to handle multiple matrices multiplication.

For instance, we have three matrices A1, A2, A3 have dimensions of 10x100, 100x5 and 5x50. If we perform the multiplication from left to right, i.e., (A1A2)A3, the total counts would be 10x100x5+10x5x50=7500, since (A1A2) will have the dimension of 10x5.

Another way of doing this is A1(A2A3), similarly, the counts would be 100x5x50+10x100x50=75000 which is 10x the first method.

So, given the number of matrices(n) and the dimension of each matrix(row col), assuming they are valid), please provide the optimal way in handling the multiplication that returns the minimum counts.

Input

First line an integer n indicates the number of matrixes.

The rest of n lines has 2 number indicate the dimension

Output

An integer

Sample Input 1

3
10 100
100 5
5 50

Sample Output 1

7500

Sample Input 2

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

Sample Output 2

15125

Constrains

1 <= N <= 100
1 <= A.row <= 100
1 <= A.col <= 100