Minimum Cost to Paint Houses

You are given a row of houses and the cost of painting each house in three different colors. Your task is to determine the minimum total cost to paint all the houses such that no two adjacent houses have the same color. For each house i (with 0-based indexing), if you choose color j for that house, the cost is given by cost[i][j], where j belongs to \( \{0, 1, 2\} \). The decision for the current house depends on the color chosen for the previous house. The recurrence relation can be represented as:

[ \text{dp}[i][j] = cost[i][j] + \min_{\substack{k=0 \ k \neq j}} { \text{dp}[i-1][k] } ]

Compute \( \min\{\text{dp}[n-1][0],\ \text{dp}[n-1][1],\ \text{dp}[n-1][2]\} \) to obtain the minimum total painting cost.

inputFormat

The input is provided via standard input (stdin). The first line contains an integer \( n \) representing the number of houses. Each of the next \( n \) lines contains three space-separated integers, which correspond to the cost of painting the house in three different colors. If \( n = 0 \), then there are no houses.

outputFormat

Output a single integer to standard output (stdout), which is the minimum total cost to paint all the houses under the given constraint.

## sample

1
10 5 20

5

</p>