Algorytmy 2

Mnożenie ciągu macierzy

Limit czasu: 1s | Limit pamięci: 64MB

Dany jest ciąg $n$ macierzy $M_i$, który chcemy wymnożyć. Mnożenie macierzy jest łączne, ale nie jest przemienne. Zakładamy, że koszt wymnożenia macierzy o wymiarach $p \times q$ przez macierz o wymiarach $q \times r$, wynosi $p\cdot q\cdot r$ mnożeń. Jaka jest minimalna możliwa liczba mnożeń potrzebna do wymnożenia wszystkich macierzy?

Wejście

Pierwszy wiersz wejścia zawiera liczbę $n$. W każdym z kolejnych $n$ wierszów dane są liczby $r_i$ i $c_i$ liczba wierszów i kolumn macierzy $M_i$.

Wyjście

Pierwszy i jedyny wiersz wyjścia zawiara minimalną liczbę mnożeń konieczną do wymnożenia wszystkich macierzy.

Ograniczenia

$1 \le n \le 100$
$1 \le r_i, c_i \le 100$

Przykłady

Wejście 1