Problem
Una fila di N persone in fila per i biglietti per la premiere del nuovo musical, ognuna delle quali vuole acquistare 1 biglietto. Solo una biglietteria ha funzionato per l'intera coda, quindi la vendita dei biglietti è stata molto lenta, portando "ospiti" code per la disperazione. I più intelligenti hanno subito notato che, di norma, un cassiere vende più biglietti in una mano più velocemente rispetto a quando gli stessi biglietti vengono venduti uno alla volta.
Pertanto, hanno suggerito a diverse persone in piedi di fila di dare dei soldi al primo di loro in modo che compri i biglietti per tutti.
Tuttavia, per combattere gli speculatori, il cassiere non vendeva più di 3 biglietti a persona, quindi solo 2 o 3 persone di fila potevano raggiungere un accordo in questo modo.
È noto che il cassiere spende Ai secondi per vendere un biglietto alla i-esima persona in coda, e Bi secondi per vendere due biglietti , tre biglietti - Ci secondi. Scrivi un programma che calcolerà il tempo minimo in cui tutti i clienti potrebbero essere serviti.
Si noti che i biglietti per un gruppo di persone unite vengono sempre acquistati dal primo di loro. Inoltre, nessuno acquista biglietti extra (ovvero biglietti di cui nessuno ha bisogno) per accelerare.
Inserimento:
- la prima riga contiene il numero N - il numero di acquirenti in coda (\(1<=N<=5000\)) ;
- poi vengono N triple di numeri naturali Ai, Bi , Ci. Ognuno di questi numeri non supera 3600. Le persone in coda sono numerate a partire dalla cassa.
Output: stampa un singolo numero: il tempo minimo in secondi in cui è possibile servire tutti i clienti.
Esempi
| # |
Input |
Uscita |
| 1 |
5
5 10 15
2 10 15
5 5 5
20 20 1
20 1 1
|
12 |
| 2 |
2
3 4 5
1 1 1
|
4 |