Задача Tickets2018.   За квитками на концерт гурту «Золоті роги»  вишикувалася черга з N фанатів, кожен з яких хоче купити 1 квиток. На всю чергу працювала лише одна каса, тому продаж квитків йшов дуже повільно. І  це дратувало фанатів гурту, що стояли в черзі. Найкмітливіші швидко помітили, що кілька квитків в одні руки касир продає швидше, ніж коли ці ж квитки продаються по одному. Тому вони надумали передавати гроші першому з них, щоб він купив квитки на всіх. Однак для боротьби зі спекулянтами касир продавала не більше 3-х квитків в одні руки, тому домовитися таким чином між собою могли лише 2 або 3  фанати, що стоять поспіль. Відомо, що на продаж i-ій людині з черги одного квитка касир витрачає Ai секунд, на продаж двох квитків - Bi секунд, трьох квитків - Ci секунд. Напишіть програму, яка підрахує мінімальний час, за який могли б придбати квитки всі фанати. Зверніть увагу, що квитки на групу фанатів завжди купує перший з них. Також ніхто  купує зайвих квитків (тобто квитків, які нікому не потрібні).

Технічні умови. Програма Tickets2018 читає з пристрою стандартного введення число  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

Введення

2

3 4 5

1 1 1

Виведення

 4

© LIKT 1998-2018