|Online MIPT programming contest||РУССКИЙ|
Time limit = 5 second(s)N mans are standing in a queue to buy tickets for a new musical. Each person wants to buy exactly one ticket. There was only one ticket window open so the booking went slowly driving guests to despair. The most intelligent ones noted that, generally, cashier sold several tickets to the one man faster, than when the same tickets were sold one by one. So, they suggested that several successive mans should hand their money over to the first of them to buy the tickets for the whole group at once.
However, the cashier struggled against profiters, and refused to sell more than three tickets to the same man, so that scheme was useful only for two or three successive persons.
It is known, it takes Ai seconds for the i-th man to buy one ticket, Bi seconds to buy two and Ci to buy three ones.
You are to find out the minimal time that whould have taken for the whole queue to get served.
Please, note that the tickets are always bought by the first person of each group. Noone speeds up the process by purchasing additional (unnessesary) tickets.
The first line contains one integer N, that is the size of the queue (1 ≤ N ≤ 5000). Than follow N triples of integers Ai, Bi, Ci, that do not exceed 3600. The mans are ordered from the ticket window.
One integer that is equal to the minimal number of seconds for the whole queue to get served.
5 5 10 15 2 10 15 5 5 5 20 20 1 20 1 1
2 3 4 5 1 1 1
© acm.mipt DevGroup
The page was generated in 210ms