Умножение матриц

Даны n матриц с размерами соответственно. Матрицы расположены слева направо в порядке от 1 до n. Разрешается расставлять скобки, чтобы менять порядок умножений.

Каково минимальное число операций, необходимое, чтобы перемножить все эти матрицы?

Входные данные

В первой строке содержится одно целое число n ().

В следующих n строках заданы размеры матриц (1 ≤ ≤ 1000).

Гарантируется, что для .

Выходные данные

Программа должна вывести минимальное число операций, необходимое для умножения всех матриц.

Примеры