POLSKI SPOJ

Tomek jest ogrodnikiem, ma założoną własną firmę. Jej motto: im mniej zapłaci klient, tym będzie bardziej radosny ;) Dostał on następujące zlecenie, ma posadzić na przed każdym domem na ulicy róże w jednym z trzech kolorów: białym, żółtym, czerwonym. Jednak z posadzeniem wiąże się również koszt, który jest różny w zależności od numeru domku oraz koloru. Zadanie wyglądało na proste, dopóki Tomek nie udał się na miejsce, gdzie okazało się ze mieszkańcy maja prośbę: chcą, aby żadni dwaj sąsiedzi nie mieli róż o takim samym kolorze (zakładamy ze dom 1 i ostatni nie są sąsiadami). Pomóż Tomkowi wykonać zadanie i napisz program, które zminimalizuje koszty i wypisze minimalny koszt.

Wejście

W pierwszej linijce wejścia znajduje się liczba n (1<=n<=100000) oznaczająca liczbę domków. Następnie n linii, w każdej linii znajdują się 3 liczby a b c (1<=a,b,c<=100) oznaczające koszty posadzenia róż (a-czerwonych, b-białych, c-żółtych), w dla każdego kolejnego domu.

Wyjście

Na wyjściu powinna pojawić się dokładnie jedna liczba oznaczająca najniższy koszt posadzenia róż zgodnie z zasadami.

Przykład 1

Wejście:
2
1 2 3
3 4 2

Wyjście:
3

Przykład 2

Wejście:
2
1 2 3
3 10 12

Wyjście:
5