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.