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
 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#15 5 10 15 2 10 15 5 5 5 20 20 1 20 1 1 Output#112
 Input#22 3 4 5 1 1 1 Output#24

Author:

 © acm.mipt DevGroupThe page was generated in 190ms