RGB Street 2

Interview

Time limit0.5sMemory limit128 MB

Summary

Paint N houses in a cycle with three colors so that every adjacent pair differs, minimizing total cost.

Level: Medium6 of 10
Topics: Dynamic programming, Implementation, Array, Brute force
Solved: No attempts yet

Problem

There are N houses on RGB Street. The street can be represented as a line segment, with house 1 through house N in order.

Each house must be painted one of red, green, or blue. Given the cost of painting each house red, green, or blue, find the minimum total cost of painting all the houses while satisfying the rules below.

The color of house 1 must differ from the colors of house 2 and house N.
The color of house N must differ from the colors of house N-1 and house 1.
For i (2 ≤ i ≤ N-1), the color of house i must differ from the colors of house i-1 and house i+1.

Input

The first line gives the number of houses N (2 ≤ N ≤ 1,000). The next N lines give the cost of painting each house red, green, and blue, one line per house starting from house 1. Each painting cost is a positive integer no greater than 1,000.

Output

Print the minimum total cost of painting all the houses on the first line.

Examples5

Example 1
Input
```
3
26 40 83
49 60 57
13 89 99
```
Expected output
```
110
```
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
```
201
```

Example 4

Input

Expected output

Example 5

Input

Expected output