Solved by 734 users: ...
UserDateAttemptTimeCMSC
sb3ar`17 feb 2008`Ruby1000.1369
sb3ar`17 feb 2008`Ruby700.1387
Belthazor`20 apr 2012`Python900.2789
sb3ar`17 feb 2008`Ruby600.1394
Belthazor`19 apr 2012`Python600.2796
Nakilon`12 jan 2010`Ruby200.11103
Belthazor`19 apr 2012`Python300.27103
Ali_taldyk`21 aug 2009`FPC100.01106
mikl`21 aug 2007`C++600.04110
mikl`21 aug 2007`C++500.04112
Vman`17 sep 2006`FPC300.01118
WsemirZ`29 dec 2007`FPC800.01118
WsemirZ`29 dec 2007`FPC1000.01118
WsemirZ`29 dec 2007`FPC900.01120
WsemirZ`29 dec 2007`FPC1100.01120
abortmozga.ru`09 jul 2010`C++3000.05120
zkw`14 may 2009`Lua100.06120
Vladislav_Simonenko`16 mar 2006`C++200.13123
 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:

 © acm.mipt DevGroupThe page was generated in 210ms