#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
const ll INF = 1e8;
const ll Nm = (1<<17); const ll E = 17;
vector<ll> stdp;
void upd(ll p, ll v) {
if (p==0) {
return;
}
stdp[p]=min(stdp[p],v);
upd(p/2,v);
}
inline ll v2(ll x) {
return __builtin_ctz(x);
}
ll gmin(ll a, ll b) {
if (a>b) {
return INF;
}
ll va = v2(a); ll vb = v2(b+1);
if (va<vb) {
return min(stdp[(a>>va)+(1<<(E-va))],gmin(a+(1<<va),b));
} else {
return min(stdp[(b>>vb)+(1<<(E-vb))],gmin(a,b-(1<<vb)));
}
}
ll minimumInstructions(ll N, ll M, ll K, vector<ll> C, vector<ll> A, vector<vector<ll>> B) {
stdp.clear();
for (ll i=0;i<(2*Nm);i++) {
stdp.push_back(INF);
}
vector<ll> indC[K];
for (ll i=0;i<M;i++) {
for (ll j=0;j<A[i];j++) {
indC[B[i][j]].push_back(i);
}
}
vector<ll> trm[M];
for (ll x=0;x<N;x++) {
for (ll y: indC[C[x]]) {
//cout << "x,y: "<<x<<","<<y<<"\n";
trm[(y+M-(x%M))%M].push_back(x);
}
}
vector<bool> isV(N-M+1,false);
for (ll m=0;m<M;m++) {
sort(trm[m].begin(),trm[m].end());
for (ll xc=0;xc<=(ll)(trm[m].size()-M);xc++) {
if ((trm[m][xc+M-1]-trm[m][xc])==(M-1)) {
isV[trm[m][xc]]=1;
//cout << "isV = 1 at "<<trm[m][xc]<<"\n";
}
}
}
if (!isV[0]) {
return -1;
}
stdp[0]=1;
upd(Nm,1);
for (ll i=1;i<=(N-M);i++) {
if (isV[i]) {
stdp[i]=min(INF,gmin(max(i-M,0),i-1)+1);
//cout << "stdp at i="<<i<<" is "<<stdp[i]<<"\n";
if (stdp[i]<INF) {
upd(i+Nm,stdp[i]);
}
}
}
if (stdp[N-M]>=INF) {
return -1;
}
return stdp[N-M];
}
