Tickets

Problem description

In front of the football stadium there is a big queue of N people each of them wants to buy 1 ticket to the final match. There is only one booking office so queue moves very slowly. Bob is a good programmer and he observed that sometimes it takes less time to buy several tickets at once. So he decided to make groups of people and first person from group could buy ticket for everyone. But according to rules one man can buy only up to 3 tickets so only 3 people in a row at most can make a group.

Bob knows that booking-clerk sells 1 ticket to the ith person in A_i seconds, 2 tickets in B_i seconds and 3 tickets in C_i seconds. When 2 or 3 people in a row make a group only first of them can buy tickets. No one buys extra tickets to speed up the queue because no one wants to give extra money.

Calculate how much time at least it will take to buy all the tickets.

Input

Line 1: A single integer: N (1 <= N <= 5000).

Line 2..Line N+1: Three integers on each line: A_i, B_i, C_i <= 3600.

Output

Single integer, minimum time in seconds.

Example