e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Dynamic Programming - Linear

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

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

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

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

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

Вхідні дані

Перше число містить кількість покупців у черзі n (1n5000). Далі йде n трійок натуральних чисел ai, bi, ci. Кожне з цих чисел не перевищує 3600. Люди у черзі нумеруються починаючи від каси.

Вихідні дані

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #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