1362: Купівля квитків


Відправити розв'язок


Бали:6
Time limit:1.0s
Memory limit:63M
Author:

Problem type

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

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

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

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

Формат вхідних даних

У вхідному потоці записано спочатку число N - кількість покупців у черзі (1 ≤ N ≤ 5000). Далі йде N трійок натуральних чисел Ai, Bi, Ci. Кожне з цих чисел не перевищує 3600. Люди в черзі нумеруються починаючи від каси.

Формат вихідних даних

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

Приклад вхідних даних

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

Приклад вихідних даних

12

Коментарі

Ще немає коментарів.