Задача 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