Given two matrices with dimensions *n*_{1} × *n*_{2} and *n*_{2} × *n*_{3},
the cost of the usual multiplication algorithm
is Θ(*n*_{1} *n*_{2} *n*_{3}).
For simplicity, let us consider that the cost is exactly *n*_{1} *n*_{2} *n*_{3}.

Suppose that we must compute
*M*_{1} × … × *M*_{m},
where every *M*_{i} is an *n*_{i} × *n*_{i+1} matrix.
Since the product of matrices is associative,
we can choose the multiplication order.
For example, to compute *M*_{1} × *M*_{2} × *M*_{3} × *M*_{4},
we could either choose (*M*_{1} × *M*_{2}) × (*M*_{3} × *M*_{4}),
with cost *n*_{1} *n*_{2} *n*_{3} + *n*_{3} *n*_{4} *n*_{5} + *n*_{1} *n*_{3} *n*_{5},
or either choose *M*_{1} × ((*M*_{2} × *M*_{3}) × *M*_{4}),
with cost *n*_{2} *n*_{3} *n*_{4} + *n*_{2} *n*_{4} *n*_{5} + *n*_{1} *n*_{2} *n*_{5},
or three other possible orders.

Write a program to find the minimum cost of computing
*M*_{1} × … × *M*_{m}.

**Input**

Input consists of several cases,
each one with *m* followed by the *m* + 1 dimensions.
Assume 2 ≤ *m* ≤ 100 and 1 ≤ *n*_{i} ≤ 10^{4}.

**Output**

For every case, print the minimum cost
to compute the product of the *m* matrices.

Public test cases

**Input**

2 1 2 3 3 10 20 30 40 10 9000 4000 3500 8000 2000 7500 6000 1000 8500 5500 7000

**Output**

6 18000 302250000000

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++