Time limit 1000/1000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
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 Ai seconds, 2 tickets in Bi seconds and 3 tickets in Ci 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: Ai, Bi, Ci <= 3600.
Output
Single integer, minimum time in seconds.
Example
| stdin |
stdout |
5
5 10 15
2 10 15
5 5 5
20 20 1
20 1 1
|
12 |
Для отправки решений необходимо выполнить вход.
|