Matrix Multiplication Order 4

Multiplying an $N \times M$ matrix $A$ by an $M \times K$ matrix $B$ takes $N \times M \times K$ multiplications in total. The number of multiplications needed to multiply $N$ matrices depends 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 2$, and consider computing the product $ABC$.

• If $AB$ is computed first and then multiplied by $C$, computing $(AB)C$ takes $5 \times 3 \times 2 + 5 \times 2 \times 2 = 30 + 20 = 50$ multiplications.
• If $BC$ is computed first and then $A$ is multiplied by it, computing $A(BC)$ takes $3 \times 2 \times 2 + 5 \times 3 \times 2 = 12 + 30 = 42$ multiplications.

The same product needs a different number 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 cannot be changed.

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

From the second line to line $N+1$, line $i+1$ contains the size $r_i$ and $c_i$ of the $i$-th matrix. ($1 \le r_i, c_i \le 10{,}000$)

The input always contains sizes that can be multiplied in order.

The sizes of the given matrices are guaranteed to be monotonically non-increasing. That is, for $1 \le i < j \le n$, $r_i \ge r_j$ and $c_i \ge c_j$.

Print the minimum number of multiplications needed to multiply the given matrices on the first line. The answer is a natural number less than or equal to $2^{63}-1$. Also, even when the matrices are multiplied in the worst order, the number of multiplications is less than or equal to $2^{63}-1$.