#pragma GCC optimize("O2,unroll-loops")
#include "paint.h"
#include<string.h>
#include<stdio.h>
#include<map>
#include<time.h>
#include<stdlib.h>
#define assert(x) if (!(x)) __builtin_trap()
int max(int i,int j){return i>j?i:j;}
int min(int i,int j){return i<j?i:j;}
#include <vector>
#define NN 100000
#define MM 50000
#define KK 100000
void push(int**eh,int*eo,int i,int j)
{
int o=eo[i]++;
if(!o)eh[i]=(int*)malloc(2*sizeof**eh);
else if(!(o&o-1))eh[i]=(int*)realloc(eh[i],2*o*sizeof**eh);
eh[i][o]=j;
}
void push_(int**eh,int*eo,int j) { return push(eh,eo,0,j); }
void clear(int**eh,int*eo,int i){eo[i]=0;free(eh[i]);eh[i]=0;}
int*eh[2],eo[2],*fh[KK],fo[KK],*ll,lo,dp[NN],*gh[2],go[2],freq[NN],*rr[NN],ro[NN],at[MM];
int get(int cc, int pp)
{
if(cc<0)return 0;
if(at[pp]==-1)return 0;
return gh[cc&1][at[pp]];
}
/* assume this function is only called once, it doesn't clear values */
int minimumInstructions(
int N, int M, int K, std::vector<int> C,
std::vector<int> A, std::vector<std::vector<int>> B) {
memset(at,-1,sizeof at);
srand(time(0));
for(int i=0;i<M;++i)
for(int j=0;j<A[i];++j)
push(fh,fo,B[i][j],i);
for(int i=0;i<N;++i)
{
clear(eh,eo,i&1);
clear(gh,go,i&1);
for(int j=0;j<fo[C[i]];++j)
push(eh,eo,i&1,fh[C[i]][j]); /* N * sqrt(4e5) ? ? */
for(int yy,j=0;j<eo[i&1];++j)
{
push(gh,go,i&1,yy=min(M,1+get(i-1,(M+eh[i&1][j]-1)%M)));
if(yy==M&&!freq[i-M+1]++)
push_(&ll,&lo,i-M+1);
}
for(int j=0;j<eo[i&1^1];++j)
at[eh[i&1^1][j]]=-1;
for(int j=0;j<eo[i&1];++j)
at[eh[i&1][j]]=j;
}
for(int i=0;i<N;++i)freq[i]=0;
for(int i=0;i<lo;++i)++freq[ll[i]];
lo=0;
for(int i=0;i<N;++i)while(freq[i]--)ll[lo++]=i;
for(int i=0;i<N;++i) dp[i]=1e9;
std::map<int,int>in={{1000000000,1}};
for(int i=0;i<N;++i)
ro[i]=0,rr[i]=0;
for(int i=0,j=0;i<N;++i)
{
while(j<lo&&ll[j]<=i)
{
int before=ll[j]==0?0:dp[ll[j]-1];
++in[before+1];
if(i+M<N)
push(rr,ro,i+M,before+1);
++j;
}
for(int j=0;j<ro[i];++j)
if(!--in[rr[i][j]])in.erase(rr[i][j]);
dp[i]=in.begin()->first;
}
return dp[N-1] >= 1e9 ? -1 : dp[N-1];
}
