A line of N people lined up for tickets to the premiere of the new musical, each of whom wants to buy 1 ticket. Only one ticket office worked for the entire queue, so ticket sales were very slow, bringing "guests" queues in desperation. The smartest ones quickly noticed that, as a rule, a cashier sells several tickets in one hand faster than when the same tickets are sold one at a time.
Therefore, they suggested that several standing people in a row give money to the first of them so that he buys tickets for everyone.
However, in order to fight speculators, the cashier sold no more than 3 tickets per person, so only 2 or 3 people in a row could reach an agreement in this way.
It is known that the cashier spends Ai seconds to sell one ticket to the i-th person in the queue, and Bi seconds to sell two tickets , three tickets - Ci seconds. Write a program that will calculate the minimum time that all customers could be served.
Note that tickets for a group of united people are always bought by the first of them. Also, no one buys extra tickets (that is, tickets that no one needs) in order to speed up.
Input:
- the first line contains the number N - the number of buyers in the queue (\(1<=N<=5000\));
- next comes N triples of natural numbers Ai, Bi, Ci. Each of these numbers does not exceed 3600. People in the queue are numbered starting from the cashier.
Output: print a single number - the minimum time in seconds that all customers could be served.
Examples
| # |
Input |
Output |
| 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 |