Покупка квитків

За квитками на прем'єру нового мюзіклу вишикувалась черга з $n$ людей, кожен з яких хоче купити один квиток. На всю чергу працювала лише одна каса, тому продаж квитків йшов дуже повільно, приводячи "постояльців" черги у відчай. Найкмітливіші швидко помітили, що, як правило, кілька квитків в одні руки касир продає швидше, ніж коли ці ж квитки продаються по одному. Тому вони запропонували декільком людям, які стоять поспіль, віддавати гроші першому з них, щоб він купив квитки на всіх.

Однак для боротьби зі спекулянтами касир продавав не більше трьох квитків в одні руки, тому домовитися таким чином між собою могли лише дві або три людини, які стоять поруч.

Відомо, що на продажу $i$-й людині з черги одного квитка касир витрачає $a_i$ секунд, на продажу двох квитків $b_i$ секунд, трьох квитків $c_i$ секунд. Напишіть програму, яка підрахує мінімальний час, за який можна обслужити усіх покупців.

Зверніть увагу, що квитки на групу людей, що об'єдналися, завжди купляє перший з них. Також ніхто з метою прискорення не купує зайвих квитків (тобто квитків, які нікому не потрібні).

Вхідні дані

Перше число містить кількість покупців у черзі $n(1\le n\le 5000)$. Далі йде $n$ трійок натуральних чисел $a_i,b_i,c_i$. Кожне з цих чисел не перевищує $3600$. Люди у черзі нумеруються починаючи від каси.

Вихідні дані

Вивести мінімальний час у секундах, за який можна обслужити усіх покупців.

Приклади