Multiplicaciones de Matrices

Dadas n matrices con dimensiones , respectivamente. Las matrices están dispuestas de izquierda a derecha, desde 1 hasta n. Se permite colocar paréntesis para dar prioridad a algunas multiplicaciones.

¿Cuál es el número mínimo de operaciones necesarias para multiplicar todas las matrices?

Entrada

La primera línea contiene un único entero n ().

Las siguientes n líneas contienen las dimensiones de cada una de las matrices (1 ≤ ≤ 1000).

Se garantiza que para .

Salida

El programa debe imprimir la cantidad mínima de operaciones requeridas para multiplicar todas las matrices.

Ejemplos