M. Покупка билетов

В очереди стоят $N$ человек, каждому нужен один билет. Касса одна, и продажа идёт медленно.

Несколько подряд стоящих людей могут договориться: они отдают деньги первому из них, и он покупает билеты на всех. Кассир продаёт не больше трёх билетов в одни руки, поэтому договориться могут только два или три подряд стоящих человека.

На продажу $i$-му человеку одного билета кассир тратит $A_i$ секунд, двух билетов — $B_i$ секунд, трёх — $C_i$ секунд. Билеты на группу всегда покупает первый из неё, и лишних билетов никто не берёт.

Найдите наименьшее время, за которое будут обслужены все покупатели.

Первая строка содержит число $N$ ($1 \le N \le 5000$).

Следующие $N$ строк содержат по три натуральных числа $A_i$, $B_i$, $C_i$, не превосходящих $3600$. Люди нумеруются от кассы.

Одно число — наименьшее время в секундах.