Minimum Painting Cost for Houses

You are given a row of n houses. Each house can be painted in one of three colors. The cost of painting each house with a certain color is given by a 2D array costs, where costs[i][j] is the cost of painting the i^th house with the j^th color (with j = 0, 1, 2).

Your task is to compute the minimum cost to paint all houses such that no two adjacent houses have the same color.

Note: When painting house i, the color chosen must not be the same as the color of the house i-1.

Mathematical formulation: For each house i (where 0 ≤ i < n) and each color c ∈ {0, 1, 2}, define dp[i][c] as the minimum cost to paint houses from 0 to i with i painted in color c. Then, for i > 0,

\(dp[i][c] = costs[i][c] + \min_{\substack{c' = 0 \\\ c' \neq c}} dp[i-1][c']\)

The answer will be \(\min(dp[n-1][0], dp[n-1][1], dp[n-1][2])\).

inputFormat

The input is read from standard input and has the following format:

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

Constraints:

• 1 ≤ n ≤ 10⁵ (depending on the environment)
• 0 ≤ cost ≤ 10⁴

outputFormat

Output to standard output a single integer: the minimum cost to paint all houses satisfying the condition that no two adjacent houses have the same color.

## sample

3
17 2 17
16 16 5
14 3 19

10

</p>