/*
We just need to check for each length K segment whether there exist a way to color them or not.
*/
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = (int)1e9;
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
vector<int> color_contractor[K];
for (int i = 0; i < M; i++) {
for (int j : B[i]) {
color_contractor[j].push_back(i);
}
}
int qc[M][N+1];
for (int i = 0; i < M; i++) {
fill(qc[i], qc[i]+N+1, 0);
}
for (int i = 0; i < N; i++) {
for (int j : color_contractor[C[i]]) {
qc[((j-i)%M+M)%M][i+1]++;
}
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j < M; j++) {
qc[j][i] += qc[j][i-1];
}
}
int dp[N+1];
fill(dp, dp+N+1, INF);
dp[0] = 0;
for (int i = 0; i+M <= N; i++) {
bool can = false;
for (int j = 0; j < M; j++) {
can |= (qc[j][i+M] - qc[j][i] == M);
}
if (can) {
for (int j = 1; j <= M; j++) {
dp[i+j] = min(dp[i+j], dp[i]+1);
}
}
}
return (dp[N] == INF ? -1 : dp[N]);
}
