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++