#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 2;
vector<int> used[maxn];
set<pair<int,int> > st;
int valid[maxn],dpv[2][maxn],dp[maxn];
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(int j=0;j<A[i];j++){
used[B[i][j]].emplace_back(i);
}
}
memset(dpv,-1,sizeof(dpv));
for(int it : used[C[N-1]]){
dpv[(N-1)&1][it] = N-1;
if(dpv[(N-1)&1][it]-(N-1)+1 >= M){
valid[N-1+M-1] = true;
}
}
for(int i=N-2;i>=0;i--){
for(int it : used[C[i]]){
if(dpv[(i+1)&1][(it+1)%M] == -1){
dpv[i&1][it] = i;
}else{
dpv[i&1][it] = dpv[(i+1)&1][(it+1)%M];
}
if(dpv[i&1][it]-i+1 >= M){
valid[i+M-1] = true;
}
}
for(int it : used[C[i+1]]){
dpv[(i+1)&1][it] = -1;
}
}
memset(dp,-1,sizeof(dp));
dp[0] = 0;
st.emplace(0,0);
for(int i=M;i<=N;i++){
if(valid[i-1] && !st.empty()){
dp[i] = 1+(*st.begin()).first;
st.emplace(dp[i],i);
}
if(dp[i-M] != -1){
st.erase(st.lower_bound(make_pair(dp[i-M],i-M)));
}
}
return dp[N];
}
