Minimum Cost for Painting Houses

You are given n houses in a row, and each house can be painted in one of three colors: red, green, or blue. The cost of painting each house in each color is provided in a n x 3 matrix.

Your task is to paint all the houses such that no two adjacent houses have the same color while minimizing the total cost.

The cost of painting the i-th house with color j is given by \(costs[i][j]\). The restriction is that for any two adjacent houses \(i\) and \(i+1\), the colors must be different.

Input: The first line contains an integer \(n\) representing the number of houses. Each of the following \(n\) lines contains three space-separated integers, representing the cost of painting that house in red, green, and blue, respectively.

Output: Output a single integer representing the minimum cost to paint all houses.

Constraints: \(1 \leq n \leq 10^5\), and each cost is a positive integer. (For simplicity, assume \(n\) is small enough for your solution if needed.)

inputFormat

The input is read from standard input (stdin). The first line contains a single integer (n), the number of houses. Each of the following (n) lines contains three space-separated integers representing the costs of painting the house red, green, and blue, respectively.

outputFormat

A single integer printed to standard output (stdout) representing the minimum total cost to paint all the houses such that no two adjacent houses have the same color.## sample

3
17 2 17
16 16 5
14 3 19

10