Multiplication de matrices

Étant donné n matrices de dimensions respectivement. Les matrices sont ordonnées de gauche à droite de 1 à n. Vous pouvez placer des parenthèses pour prioriser certaines multiplications.

Quel est le nombre minimal d’opérations pour multiplier toutes les matrices ?

Entrée

La première ligne contient un seul entier n ().

Les n lignes suivantes contiennent les dimensions de chacune des matrices (1 ≤ ≤ 1000).

Il est garanti que pour .

Sortie

Le programme doit afficher le nombre minimal d’opérations requis pour multiplier toutes les matrices.

Exemples