Problem
Uma fila de N pessoas fez fila para comprar ingressos para a estreia do novo musical, cada uma querendo comprar 1 ingresso. Apenas uma bilheteria funcionou para toda a fila, então a venda de ingressos foi muito lenta, trazendo "convidados" filas em desespero. Os mais espertos perceberam rapidamente que, via de regra, um caixa vende vários ingressos em uma mão mais rápido do que quando os mesmos ingressos são vendidos um a um.
Portanto, eles sugeriram que várias pessoas em pé em fila dessem dinheiro ao primeiro deles para que ele comprasse ingressos para todos.
No entanto, para combater os especuladores, o caixa não vendia mais do que 3 ingressos por pessoa, então apenas 2 ou 3 pessoas seguidas poderiam chegar a um acordo dessa forma.
Sabe-se que o caixa gasta Ai segundos para vender um ingresso para a i-ésima pessoa na fila, e Bi segundos para vender dois ingressos, três ingressos - Ci segundos. Escreva um programa que calcule o tempo mínimo que todos os clientes podem ser atendidos.
Observe que os ingressos para um grupo de pessoas reunidas são sempre comprados pelo primeiro deles. Além disso, ninguém compra passagens extras (ou seja, passagens de que ninguém precisa) para acelerar.
Entrada:
- a primeira linha contém o número N - o número de compradores na fila (\(1<=N<=5000\)) ;
- em seguida vem N triplos de números naturais Ai, Bi , Ci. Cada um desses números não excede 3600. As pessoas na fila são numeradas a partir do caixa.
Saída: imprime um único número - o tempo mínimo em segundos que todos os clientes podem ser atendidos.
Exemplos
| # |
Entrada |
Saída |
| 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 |