Задачі
Покупка квитків
Покупка квитків
За квитками на прем'єру нового мюзіклу вишикувалась черга з $n$ людей, кожен з яких хоче купити один квиток. На всю чергу працювала лише одна каса, тому продаж квитків йшов дуже повільно, приводячи "постояльців" черги у відчай. Найкмітливіші швидко помітили, що, як правило, кілька квитків в одні руки касир продає швидше, ніж коли ці ж квитки продаються по одному. Тому вони запропонували декільком людям, які стоять поспіль, віддавати гроші першому з них, щоб він купив квитки на всіх.
Однак для боротьби зі спекулянтами касир продавав не більше трьох квитків в одні руки, тому домовитися таким чином між собою могли лише дві або три людини, які стоять поруч.
Відомо, що на продажу $i$-й людині з черги одного квитка касир витрачає $a_i$ секунд, на продажу двох квитків $b_i$ секунд, трьох квитків $c_i$ секунд. Напишіть програму, яка підрахує мінімальний час, за який можна обслужити усіх покупців.
Зверніть увагу, що квитки на групу людей, що об'єдналися, завжди купляє перший з них. Також ніхто з метою прискорення не купує зайвих квитків (тобто квитків, які нікому не потрібні).
\InputFile
Перше число містить кількість покупців у черзі $n~(1 \le n \le 5000)$. Далі йде $n$ трійок натуральних чисел $a_i, b_i, c_i$. Кожне з цих чисел не перевищує $3600$. Люди у черзі нумеруються починаючи від каси.
\OutputFile
Вивести мінімальний час у секундах, за який можна обслужити усіх покупців.
Вхідні дані #1
5 5 10 15 2 10 15 5 5 5 20 20 1 20 1 1
Вихідні дані #1
12
Вхідні дані #2
2 3 4 5 1 1 1
Вихідні дані #2
4