A hostel corridor has N rooms in a row. Each room can be painted red, green, or blue. For every room, the cost of each color is different. To avoid a dull-looking corridor, two adjacent rooms cannot have the same color.

Find the minimum total painting cost.

The twist: choosing the cheapest color for the current room may block a better choice for the next room.

The first line contains an integer KaTeX can only parse string typed expression — the number of rooms.

Each of the next KaTeX can only parse string typed expression lines contains three integers KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, and KaTeX can only parse string typed expression — the cost of painting room KaTeX can only parse string typed expression red, green, and blue.

Print a single integer — the minimum total painting cost.