Minimum Cost to Paint Houses

Given N houses and K colors, determine the minimum total cost to paint all the houses such that no two adjacent houses are painted with the same color. Each house has K possible colors with associated painting costs provided in an N×K matrix.

The recurrence relation for the minimum cost is given by:
(dp[i][j] = cost[i][j] + \min_{m \neq j}(dp[i-1][m]))

where (dp[i][j]) represents the minimum cost to paint up to the i-th house with the j-th color.

The first line of input contains two integers N and K. The next N lines each contain K space-separated integers representing the cost for each house and each color.

inputFormat

The first line contains two integers N and K separated by a space. Each of the following N lines contains K integers, where the j-th integer in the i-th line represents the cost of painting the i-th house with the j-th color.

outputFormat

Output a single integer which is the minimum cost to paint all houses while ensuring that no two adjacent houses have the same color.## sample

3 3
1 5 3
2 9 4
3 6 7

8