Dynamic Programming - Linear
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 most smart 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 a number of 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 (1 ≤ n ≤ 5000). Then n triples of positive integers
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.
5 5 10 15 2 10 15 5 5 5 20 20 1 20 1 1
2 3 4 5 1 1 1