АВТ
Language: Russian
English

Remote Training on Programming

Problems Online status Contests
News FAQ E-learning
For authors:
Register  ||  Login
 
Hello, Guest! Please login or register.

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

Time Limit: 1 seconds
Memory Limit:65536KB
Points:100
View Problem Statistics Submit Problem added debug

За билетами на премьеру нового мюзикла выстроилась очередь из N человек, каждый из которых хочет купить 1 билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно, приводя "постояльцев" очереди в отчаяние. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продаёт быстрее, чем когда эти же билеты продаются по одному. Поэтому они предложили нескольким подряд стоящим людям отдавать деньги первому из них, чтобы он купил билеты на всех.

Однако, для борьбы со спекулянтами кассир продавала не более трёх билетов в одни руки, поэтому договориться таким образом между собой могли лишь 2 или 3 подряд стоящих человека.

Известно, что на продажу i-му человеку из очереди одного билета кассир тратит Ai секунд, на продажу двух билетов - Bi секунд, трех билетов - Ci секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели.

Обратите внимание, что билеты на группу объединившихся людей всегда покупает первый из них. Также никто в целях ускорения не покупает лишних билетов (то есть билетов, которые никому не нужны).

Input

Во входных данных записано сначала число N - количество покупателей в очереди (1 ≤ N ≤ 5000). Далее идёт N троек натуральных чисел Ai, Bi, Ci. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются начиная от кассы.

Output

Выведите одно число - минимальное время в секундах, за которое могли быть обслужены все покупатели.

Sample

InputOutput
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

View Problem Statistics Submit Problem discussion Author/source:
Educational Courses / Problems from olympiads.ru /
773. 237 - Шаблон и слово 774. 5. 239 - Patterns 68. 240 - Equation with Missing Digits 775. 241 - Сжатие текста
Problems from Contests / School olympiads of Vologda region / Impulse, september 2020 / Impulse-2020, DP /
754. 03 - Столовские котлеты 774. 1493. 05 - How to Get One 14. 06 - Expression 867. 07 - Heap of Stones - 1
time generating 0.125 sec.
© Copyright VSU, AVT, Nosov D.A., Andrianov I.A.