RGB Street

There are N houses arranged in a line, numbered from 1 to N.

Each house must be painted one of three colors: red, green, or blue. Given the cost of painting each house in each color, find the minimum total cost to paint all houses while satisfying all of the following rules.

• The color of house 1 must be different from the color of house 2.
• The color of house N must be different from the color of house N-1.
• For every i with 2 ≤ i ≤ N-1, the color of house i must be different from the colors of houses i-1 and i+1.

The first line contains the number of houses N. (2 ≤ N ≤ 1,000)

Each of the next N lines contains three costs for one house, in order from house 1 to house N: the cost to paint it red, green, and blue. Every cost is a natural number between 1 and 1,000 inclusive.

Print the minimum cost required to paint all houses while satisfying the rules.