Dynamic programming - linear

Buying tickets

There is a queue of n people to buy tickets to a musical premiere. Each person wants to buy exactly one ticket. Only one ticket-office was working, therefore ticketing was very slowly, bringing "guests" to despair. The smartest people quickly noticed that, as a rule, the cashier sells several tickets in one hand faster than when those same tickets are sold one by one. So, they proposed for several people standing in a row to give money to the first one of them, so that he would buy tickets for all.

However, to deal with speculators, the cashier decided to sell maximum of three tickets per person, so to agree with each other in such way can only two or three successive persons.

It is known that to sell one ticket for the i-th person in the queue takes ai seconds, to sell two tickets takes bi seconds, to sell three tickets takes ci seconds. Write a program that calculates the minimum time to serve all the customers.

Please note that tickets for a group of united people always buys the first one. Also, no one buys extra tickets for speeding up the process (i.e. the tickets that are not wanted).


The first line contains the number of people in the queue n (1n5000). Then n triples of positive integers ai, bi, ci are given. Each of these numbers is not greater than 3600. People in the queue are numbering starting from the booking office.


Print the minimum time in seconds to serve all customers.

Time limit 1 second
Memory limit 128 MiB
Input example #1
5 10 15
2 10 15
5 5 5
20 20 1
20 1 1
Output example #1
Input example #2
3 4 5
1 1 1
Output example #2