I saw this problem here challenge:

Painting buildings There are N buildings in a locality. Each building must be painted with a type of paint. Initially, some buildings are painted with some type of paint. The building that is painted cannot be painted again. You are given M types of paints, 1 to M inclusive. The specialty of the locality is defined as the number of contiguous buildings that are painted with the same type of paint. For example, if six buildings apartment are painted from left to right are {1, 2, 1, 1, 3, 3}, then the likelihood of the apartment is 4 [{1}, {2}, {1, 1}, and {3, 3}]. You are given N x M matrix, where the ith row and jth column denote the painting cost of the ith building with the jth the type of paint.

You are required to determine the minimum cost to paint all the buildings such that the specialty of the apartment is exactly K. If it is not impossible to paint all buildings such that the likelihood of the apartment is exactly K, the print -1.

Input Format 1. The first line contains T denoting the number of test cases. 2. For each test case: a. The next line contains N, M, and K where N is the number of buildings in locality, M is the number of type of paints, and K is the specialty of the locality respectively. b.The next line contains N space-separated integers where the ith integer is either 0 or the type of paint from which the ith building is already painted. Here, 0 means that the building is not painted. c. The next N lines contain M space-separated integers where the ith row and jth the column denote the painting cost (cost[i,j]) of the ith building with the jth type of paint.

Output Format Print the minimum cost to paint all buildings such that the specialty of the apartment is exactly K. If it is not possible to paint all building such that the likelihood of the apartment is exactly K, then print -1.

Constraints
1 <= T <= 10
1 <= K <= N <= 100
1 <= M <= 100
1 <= cost[i, j] <= 10^9

Sample Input:
1
4 2 1
0 0 0 2
100 20
30 59
71 81
9 200
Sample Output:
160

I couldn't able to figure out how to solve this problem. Is it a graph problem, disjoint sets, ..? Can anyone give me a idea on how to solve this problem.