Module: Dinámica unidimensional

Una fila de N personas en fila para comprar entradas para el estreno del nuevo musical, cada una de las cuales quiere comprar 1 entrada. Solo funcionaba una taquilla para toda la cola, por lo que la venta de entradas era muy lenta, trayendo "invitados" colas desesperadas. Los más inteligentes notaron rápidamente que, por regla general, un cajero vende varios boletos en una mano más rápido que cuando los mismos boletos se venden de uno en uno.

Por lo tanto, sugirieron que varias personas de pie en fila le den dinero al primero de ellos para que compre boletos para todos.

 

Sin embargo, para luchar contra los especuladores, el cajero no vendía más de 3 boletos por persona, por lo que solo 2 o 3 personas seguidas podían llegar a un acuerdo de esta manera.

 

Se sabe que el cajero gasta Ai segundos para vender un boleto a la i-ésima persona en la cola, y Bi segundos para vender dos boletos, tres boletos - Ci segundos. Escriba un programa que calcule el tiempo mínimo en que todos los clientes podrían ser atendidos.

 

Tenga en cuenta que las entradas para un grupo de personas unidas siempre las compra el primero. Además, nadie compra boletos adicionales (es decir, boletos que nadie necesita) para acelerar.

 

Entrada: 
- la primera línea contiene el número N - el número de compradores en la cola (\(1<=N<=5000\)) ;
- luego viene N triples de números naturales Ai, Bi , Ci. Cada uno de estos números no supera los 3600. Las personas en la cola se numeran a partir del cajero.

 

Salida: imprime un solo número: el tiempo mínimo en segundos en que se puede atender a todos los clientes.