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