Buying tickets

There is a queue of $n$ people to buy tickets to a musical premiere. Each person wants to buy exactly one ticket. Only one ticket-office was working, therefore ticketing was very slowly, bringing "guests" to despair. The smartest people quickly noticed that, as a rule, the cashier sells several tickets in one hand faster than when those same tickets are sold one by one. So, they proposed for several people standing in a row to give money to the first one of them, so that he would buy tickets for all.

However, to deal with speculators, the cashier decided to sell maximum of three tickets per person, so to agree with each other in such way can only two or three successive persons.

It is known that to sell one ticket for the $i$-th person in the queue takes $a_i$ seconds, to sell two tickets takes $b_i$ seconds, to sell three tickets takes $c_i$ seconds. Write a program that calculates the minimum time to serve all the customers.

Please note that tickets for a group of united people always buys the first one. Also, no one buys extra tickets for speeding up the process (i.e. the tickets that are not wanted).

Input

The first line contains the number of people in the queue $n(1\le n\le 5000)$. Then $n$ triples of positive integers $a_i,b_i,c_i$ are given. Each of these numbers is not greater than $3600$. People in the queue are numbering starting from the booking office.

Output

Print the minimum time in seconds to serve all customers.

Examples