<PREV Problem:
NEXT>
Solved by 717 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Queue for tickets

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.

Input
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.

Output
One integer that is equal to the minimal number of seconds for the whole queue to get served.

Input#1
5
5 10 15
2 10 15
5 5 5
20 20 1
20 1 1
Output#1
12

Input#2
2

3 4 5
1 1 1

Output#2
4

Author:

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 23.20.13.165