#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A, vector<vector<int>> B) {
vector<int> dp(N+1,INF);
vector<vector<int>> s(K);
for(int i=0;i<M;i++){
for(int j:B[i]){
s[j].push_back(i);
}
}
int can=0;
vector<int> cnt(M);
auto add=[&](int place,int x)->void {
for(int j1:s[C[place]]){
int j=((j1-place)%M+M)%M;
can-=(cnt[j]==M);
cnt[j]+=x;
can+=(cnt[j]==M);
}
};
deque<int> d;
d.push_back(0);
dp[0]=0;
for(int i=0;i<M-1;i++){
add(i,1);
}
for(int i=M;i<=N;i++){
add(i-1,1);
while(d.size()&&d.front()<i-M){
d.pop_front();
}
if(can){
dp[i]=dp[d.front()]+1;
}
while(d.size()&&dp[d.back()]>dp[i]){
d.pop_back();
}
d.push_back(i);
add(i-M,-1);
}
return (dp[N]>=INF?-1:dp[N]);
return 0;
}
