Help needed - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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.