#include"paint.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int INF=1e9;
int cnt[MAXN],cc[MAXN],dp[MAXN];
vector<int> vi[MAXN],vop[MAXN];
bool ck[MAXN];
void update(int i,int val)
{
cc[cnt[i]]--;
cc[cnt[i]+=val]++;
}
int minimumInstructions(int N,int M,int K,vector<int> C,vector<int> A,vector< vector<int> > B)
{
for(int i=0;i<M;i++) for(auto v:B[i]) vi[v].push_back(i);
for(int i=0;i<N;i++)
{
for(auto v:vi[C[i]])
{
int pos=((v-i)%M+M)%M;
vop[max(0,i-M+1)].push_back(pos+1);
vop[i+1].push_back(-pos-1);
}
}
for(int i=0;i<=N-M;i++)
{
for(auto v:vop[i]) if(v>0) update(v,1);
else update(-v,-1);
if(cc[M]) ck[i+M]=true;
}
deque<int> dq;
dq.push_back(0);
for(int i=1;i<=N;i++)
{
if(ck[i])
{
if(!dq.empty()) dp[i]=dp[dq.front()]+1;
else dp[i]=INF;
}
else dp[i]=INF;
while(!dq.empty()&&dp[dq.back()]>=dp[i]) dq.pop_back();
dq.push_back(i);
if(dq.front()==i-M) dq.pop_front();
}
if(dp[N]>N) return -1;
return dp[N];
}
