<PREV Problem:
NEXT>
Solved by 734 users: ...
UserDateAttemptTimeCMSC
sb3ar17 feb 2008Ruby1000.1369 
sb3ar17 feb 2008Ruby700.1387 
Belthazor20 apr 2012Python900.2789 
sb3ar17 feb 2008Ruby600.1394 
Belthazor19 apr 2012Python600.2796 
Nakilon12 jan 2010Ruby200.11103 
Belthazor19 apr 2012Python300.27103 
Ali_taldyk21 aug 2009FPC100.01106 
mikl21 aug 2007C++600.04110 
mikl21 aug 2007C++500.04112 
Vman17 sep 2006FPC300.01118 
WsemirZ29 dec 2007FPC800.01118 
WsemirZ29 dec 2007FPC1000.01118 
WsemirZ29 dec 2007FPC900.01120 
WsemirZ29 dec 2007FPC1100.01120 
abortmozga.ru09 jul 2010C++3000.05120 
zkw14 may 2009Lua100.06120 
Vladislav_Simonenko16 mar 2006C++200.13123 
Languages
C++
374
FPC
167
C
118
Kylix
42
Java
35
Ruby
5
Python
2
Lua
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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 180ms

SW soft NIX
ID = 18.232.51.247