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

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

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

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

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

5
5 10 15
2 10 15
5 5 5
20 20 1
20 1 1

12

2
3 4 5
1 1 1

4