Minimum Cost to Paint Houses

You are given an N x N matrix where the element at the i-th row and j-th column represents the cost of painting the i-th house with the j-th color. There are exactly N houses and N available colors, and you must paint every house such that no two adjacent houses share the same color. Your task is to find the minimum total cost required to paint all houses.

The problem can be modeled using dynamic programming. The recurrence relation is given by:

$$dp(i,j) = cost(i,j) + \min_{\substack{0 \leq k < N \\\ k \neq j}} dp(i-1,k) $$

The answer is:

$$\min_{0 \leq j < N} dp(N-1,j)$$

The input begins with an integer N, followed by N lines each containing N space-separated integers representing the cost matrix. The output is a single integer representing the minimum total cost to paint all houses.

inputFormat

The first line of input contains an integer N representing the number of houses (and colors). Each of the next N lines contains N space-separated integers, where the j-th integer of the i-th line represents the cost to paint the i-th house with the j-th color.

outputFormat

Output a single integer which is the minimum total cost to paint all houses under the given constraints.## sample

3
17 2 17
16 16 5
14 3 19

10