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

3
10 100
100 5
5 50

Wyjście 1

7500