Minimize Painting Cost

You are given a sequence of n buildings and k available colors. The cost to paint the i-th building with the j-th color is given by \(c_{i,j}\). You must paint all buildings such that no two adjacent buildings have the same color. That is, for every \(1 \leq i < n\), the constraint \(color(i) \neq color(i+1)\) must be satisfied.

Your task is to compute the minimum total cost required to paint all buildings.

inputFormat

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

1. The first line contains two integers, n and k, where n is the number of buildings and k is the number of available colors.
2. The next n lines each contain k space-separated integers. The j-th integer in the i-th line represents \(c_{i,j}\), the cost to paint the i-th building with the j-th color.

outputFormat

Output to stdout a single integer: the minimum total cost to paint all the buildings following the rule that no two adjacent buildings share the same color.

1 3
1 2 3

1