Matrix chain multiplication order

Multiplying an $N \times M$ matrix $A$ by an $M \times K$ matrix $B$ takes $N \times M \times K$ scalar multiplications. When several matrices are multiplied, the total number of scalar multiplications depends on the order in which the products are taken.

Suppose $A$ is $5 \times 3$, $B$ is $3 \times 2$, and $C$ is $2 \times 6$. There are two orders for computing the product $ABC$.

• Multiplying $AB$ first and then multiplying by $C$ costs $5 \times 3 \times 2 + 5 \times 2 \times 6 = 30 + 60 = 90$ scalar multiplications for $(AB)C$.
• Multiplying $BC$ first and then multiplying $A$ on the left costs $3 \times 2 \times 6 + 5 \times 3 \times 6 = 36 + 90 = 126$ scalar multiplications for $A(BC)$.

The resulting matrix is the same, but the count of operations changes with the order.

Given the sizes of $N$ matrices, write a program that finds the minimum number of scalar multiplications needed to multiply all of them. You must not reorder the matrices given in the input.

The first line contains the number of matrices $N$. ($1 \le N \le 500$)

Each of the next $N$ lines contains the size $r$ and $c$ of one matrix, in the order the matrices are multiplied. ($1 \le r, c \le 500$)

The input always describes sizes that can be multiplied in the given order. That is, the column count of the $i$-th matrix equals the row count of the $(i+1)$-th matrix.

Print the minimum number of scalar multiplications needed to multiply all the given matrices. The answer is at most $2^{31}-1$. Even the worst order takes at most $2^{31}-1$ operations.