Matrix Multiplications

Given n matrices $A_1,A_2,…,A_n$ with sizes $a_1×b_1, a_2×b_2,…,a_n×b_n$, 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?

Input

The first line contains a single integer n ($2 ≤ n ≤ 300$).

The next n lines contain the dimensions of each of the matrices $a_i, b_i$ (1 ≤ $a_i, b_i$ ≤ 1000).

It’s guaranteed that $b_i = a_{i+1}$ for $i \in \{1, 2, ..., n-1\}$.

Output

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

Examples