636. Paint House

0

Easy

A row of **n** houses needs to be painted, with each house having the option to be painted red, blue, or green. The cost of painting each house with a specific color varies. The objective is to paint all the houses in a way that no two **adjacent** houses have the same color. The costs of painting each house with a specific color are represented by an **n*3 cost** matrix called 'costs'. For example, costs represents the cost of painting house 0 with the color red, costs represents the cost of painting house 1 with the color green, and so on. Find the minimum cost required to paint all the houses.

Input Format

The first line contains an integer 'n' representing the total number of houses. The following 'n' lines each contain three space-separated integers representing the cost of painting a house with red, blue, and green respectively.

Output Format

Print the minimum cost required to paint all the houses.

Example

Input

3 17 2 17 16 16 5 14 3 19

Output

10

Constraints

1<= n <= 104
1 <= cost[i][j] <= 100