#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int check[20005];
bool ee[20005];
int minimumInstructions(
int N, int M, int K, std::vector<int> C,
std::vector<int> A, std::vector<std::vector<int>> B) {
memset(ee, false, sizeof(ee));
vector<set<int>> allowed(K);
for (int i = 0; i < M; i ++) {
for (auto a : B[i])
allowed[a].insert(i);
}
for (int i = 0; i < M; i ++) {
memset(check, 0, sizeof(check));
int cur = i;
for (int j = 0; j < N; j ++) {
if (!allowed[C[j]].count(cur)) {
check[j] ++;
check[min(N, j + M)] --;
}
cur = (cur + 1) % M;
}
for (int j = 1; j < N; j ++)
check[j] += check[j - 1];
for (int j = 0; j < N; j ++)
ee[j] |= (check[j] == 0);
}
vector<int> dp(N + 1);
dp[0] = 0;
multiset<int> curmins;
curmins.insert(0);
for (int i = 1; i < M; i ++)
dp[i] = 1e9, curmins.insert(1e9);
for (int i = M; i <= N; i ++) {
int best = 1e9;
if (ee[i - 1]) {
best = min(best, *curmins.begin() + 1);
}
dp[i] = best;
curmins.erase(curmins.find(dp[i - M]));
curmins.insert(best);
}
// for (auto a : dp)
// cout << a << " "; cout << endl;
// for (int i = 0; i < N; i ++)
// cout << ee[i] << " "; cout << endl;
if (dp[N] == 1e9)
return -1;
return dp[N];
}
