Given a sequence of matrices, find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications.

We have many options to multiply a chain of matrices because matrix multiplication is associative. In other words, no matter how we parenthesize the product, the result will be the same. For example, if we had four matrices A, B, C, and D, we would have: \[ (ABC)D = (AB)(CD) = A(BCD) = \ldots \] However, the order in which we parenthesize the product affects the number of simple arithmetic operations needed to compute the product, or the efficiency.

For example, suppose $$A$$ is a $$10 \times 30$$ matrix, $$B$$ is a $$30 \times 5$$ matrix, and $$C$$ is a $$5 \times 60$$ matrix. Then, \[ (AB)C = (10 \times 30 \times 5) + (10 \times 5 \times 60) = 1500 + 3000 = 4500\ \text{multiplications} \] whereas \[ A(BC) = (30 \times 5 \times 60) + (10 \times 30 \times 60) = 9000 + 18000 = 27000\ \text{multiplications} \] Clearly the first parenthesization requires fewer number of operations.

Assignment

Write a function matrixChainOrder that takes a sequence (a list or a tuple) of integers that represents the chain of matrices, such that the $$i$$-th matrix $$A_i$$ is of dimension $$p_{i-1} \times p_i$$. The function must return the minimum number of multiplications needed to multiply the chain.

Example

>>> matrixChainOrder((40, 20, 30, 10, 30))
26000
>>> matrixChainOrder([10, 20, 30, 40, 30])
30000
>>> matrixChainOrder((10, 20, 30))
6000