RGB Street

Interview

Time limit0.5sMemory limit128 MB

Summary

Given per-house costs for three colors, compute the minimum total cost to paint all houses in a line so that no two adjacent houses share a color.

Level: Easy3 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples5

Example 1
Input
```
3
26 40 83
49 60 57
13 89 99
```
Expected output
```
96
```
Example 2
Input
```
3
1 100 100
100 1 100
100 100 1
```
Expected output
```
3
```
Example 3
Input
```
3
1 100 100
100 100 100
1 100 100
```
Expected output
```
102
```

Example 4

Input

Expected output

Example 5

Input

Expected output