Matrixmultiplikationen

Gegeben sind n Matrizen mit den Abmessungen . Die Matrizen sind von links nach rechts mit den Indizes 1 bis n angeordnet. Es ist erlaubt, Klammern so zu setzen, dass bestimmte Multiplikationen bevorzugt ausgeführt werden.

Gesucht ist die minimale Anzahl von Operationen, um alle Matrizen zu multiplizieren.

Eingabe

Die erste Zeile enthält eine einzelne ganze Zahl n ().

Die folgenden n Zeilen enthalten die Dimensionen jeder Matrix (1 ≤ ≤ 1000).

Es gilt für .

Ausgabe

Das Programm soll die minimale Anzahl an Operationen ausgeben, die erforderlich ist, um alle Matrizen zu multiplizieren.

Beispiele