Minimum Cost to Paint Houses

You are given n houses in a row, where each house can be painted in one of three colors. The cost of painting each house in a particular color is given in a matrix form. The goal is to determine the minimum cost to paint all the houses such that no two adjacent houses have the same color.

Mathematically, let \(cost[i][j]\) be the cost of painting the \(i^{th}\) house with color \(j\) (where \(j \in \{0, 1, 2\}\)). For every house \(i \ge 1\), the cost is updated as:

[ \begin{aligned} cost[i][0] &\leftarrow cost[i][0] + \min(cost[i-1][1],, cost[i-1][2]),\ cost[i][1] &\leftarrow cost[i][1] + \min(cost[i-1][0],, cost[i-1][2]),\ cost[i][2] &\leftarrow cost[i][2] + \min(cost[i-1][0],, cost[i-1][1]). \end{aligned} ]

The answer is the minimum of the values in the last row, i.e., \(\min(cost[n-1][0],\, cost[n-1][1],\, cost[n-1][2])\). If there are no houses (i.e. \(n = 0\)), the cost is 0.

inputFormat

The input is read from standard input (stdin):

1. The first line contains an integer \(n\) representing the number of houses.
2. The next \(n\) lines each contain three space-separated integers representing the cost of painting the corresponding house in three colors.

outputFormat

Output a single integer to standard output (stdout) representing the minimum total cost to paint all houses under the given constraints.

## sample

3
17 2 17
16 16 5
14 3 19

10

</p>