Algorithms and Data Structures

Matrix Multiplications

Given n matrices with sizes , respectively. The matrices are ordered from left to right from 1 to n. You are allowed to place brackets to prioritize some multiplications.
What is the minimum number of operations to multiply all the matrices?
💡
When multiplying a matrix by matrix, we perform operations.

Input

The first line contains a single integer n ().
The next n lines contain the dimensions of each of the matrices (1 ≤ ≤ 1000).
It’s guaranteed that for .

Output

The program should print the minimum number of operations required to multiply all the matrices.

Examples

Input
Output
3 2 3 3 4 4 6
72

Constraints

Time limit: 4.5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue