Help needed - Codeforces

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	Dominater069	154
8	awoo	154
10	luogu_official	150

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.