# Optimal Matrix Multiplication P11455

Statement

thehtml

Given two matrices with dimensions n1 × n2 and n2 × n3, the cost of the usual multiplication algorithm is Θ(n1 n2 n3). For simplicity, let us consider that the cost is exactly n1 n2 n3.

Suppose that we must compute M1 × … × Mm, where every Mi is an ni × ni+1 matrix. Since the product of matrices is associative, we can choose the multiplication order. For example, to compute M1 × M2 × M3 × M4, we could either choose (M1 × M2) × (M3 × M4), with cost n1 n2 n3 + n3 n4 n5 + n1 n3 n5, or either choose M1 × ((M2 × M3) × M4), with cost n2 n3 n4 + n2 n4 n5 + n1 n2 n5, or three other possible orders.

Write a program to find the minimum cost of computing M1 × … × Mm.

Input

Input consists of several cases, each one with m followed by the m + 1 dimensions. Assume 2 ≤ m ≤ 100 and 1 ≤ ni ≤ 104.

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