Matrix Multiplication Order 2

A matrix $A$ of size $N \times M$ and a matrix $B$ of size $M \times K$ need $N \times M \times K$ multiplications to multiply. Multiplying $N$ matrices takes a different number of multiplications depending on the order in which they are multiplied.

For example, suppose $A$ is $5 \times 3$, $B$ is $3 \times 2$, and $C$ is $2 \times 6$, and consider computing the product $ABC$.

• Multiplying $AB$ first and then $C$, $(AB)C$ takes $5 \times 3 \times 2 + 5 \times 2 \times 6 = 30 + 60 = 90$ multiplications.
• Multiplying $BC$ first and then $A$, $A(BC)$ takes $3 \times 2 \times 6 + 5 \times 3 \times 6 = 36 + 90 = 126$ multiplications.

The same product can need different numbers of multiplications depending on the order.

Given the sizes of $N$ matrices, write a program that finds the minimum number of multiplications needed to multiply all of them. The order of the input matrices must not be changed.

The first line contains the number of matrices $N$ ($1 \le N \le 20{,}000$).

From the second line on, each of the next $N$ lines contains the size $r$ and $c$ of a matrix. ($1 \le r, c \le 10{,}000$)

Only sizes that can be multiplied in order are given.

Print the minimum number of multiplications needed to multiply the input matrices on the first line. The answer is a positive integer no greater than $2^{63}-1$. Even the worst order of operations uses no more than $2^{63}-1$ multiplications.