Minimum House Painting Cost

You are given n houses in a row. Each house can be painted in one of three colors: Red, Green, or Blue. The cost of painting each house in one of these colors is represented by a 2D array \(\textbf{costs}\), where \(\textbf{costs}[i][0]\), \(\textbf{costs}[i][1]\) and \(\textbf{costs}[i][2]\) denote the cost of painting the \(i^{th}\) house in Red, Green, and Blue respectively.

You need to paint all the houses in such a way that no two adjacent houses have the same color, while minimizing the total cost.

The recurrence relations for the dynamic programming solution are given by:

[ \begin{aligned} cost[i][0] &= cost[i][0] + \min(cost[i-1][1],; cost[i-1][2]) \[6pt] cost[i][1] &= cost[i][1] + \min(cost[i-1][0],; cost[i-1][2]) \[6pt] cost[i][2] &= cost[i][2] + \min(cost[i-1][0],; cost[i-1][1]) \end{aligned} ]

The answer is the minimum value among the three choices for the last house:

[ \min(cost[n-1][0],; cost[n-1][1],; cost[n-1][2]) ]

inputFormat

The input is read from standard input (stdin) with the following format:

• The first line contains an integer \(n\) representing the number of houses.
• If \(n > 0\), then there are \(n\) lines that follow, each containing three space-separated integers. The three integers on each line represent the cost of painting the corresponding house in Red, Green, and Blue respectively.

outputFormat

Print a single integer to standard output (stdout): the minimum cost to paint all the houses subject to the constraint that no two adjacent houses have the same color.

## sample

3
17 2 17
16 16 5
14 3 19

10