#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int nax = 1e5 + 3;
vector<int>cand[nax], col_to_wall[nax];
bool good[nax];
int tag[nax];
int curtag = 1;
int vis[nax];
int to[nax];
// void dfs(int v) {
// if(vis[v]==2) return;
// if(vis[v]==1) {
// ans = min(ans, curtag - tag[v]);
// return;
// }
// vis[v] = 1;
// tag[v] = curtag++;
// dfs(to[v]);
// vis[v] = 2;
// }
int minimumInstructions(
int N, int M, int K, vector<int> C,
vector<int> A, vector<vector<int>> B) {
for(int i=0; i<N; ++i) {
col_to_wall[C[i]].push_back(i);
}
for(int i=0; i<M; ++i) {
for(int j=0; j<A[i]; ++j) {
for(int x : col_to_wall[B[i][j]]) {
cand[x].push_back(i);
}
}
}
for(int i=0; i<N; ++i) {
sort(cand[i].begin(), cand[i].end());
}
// for(int i=0; i<N; ++i) {
// for(int j : cand[i]) {
// cerr<<j<< ' ';
// }
// cerr<<'\n';
// }
for(int i=0; i<=N-M; ++i) {
for(int j : cand[i]) {
bool yasss = true;
for(int l=0; l<M; ++l) {
yasss &= binary_search(cand[i+l].begin(),
cand[i+l].end(), (j+l)%M);
}
good[i] |= yasss;
}
}
// for(int i=0; i<N; ++i) {
// cerr<<good[i]<<' ';
// }
// cerr<<'\n';
if(!good[0]) return -1;
int last = 0, pending = -1;
int ans = 1;
for(int i=1; i<N; ++i) {
if(good[i]) {
pending = i;
}
if(last+M==i) {
if(pending==-1) return -1;
last = pending;
pending = -1;
++ans;
}
}
return ans;
// queue<int>q;
// for(int i=M-1; i>=0; --i) {
// if(good[i]) {
// q.push(i);
// }
// }
// for(int i=N-1; i>=0; --i) {
// if(!q.empty()) {
// if((i+M)%N<q.front() || ((i+M)==N-1 && q.front()==0)) {
// q.pop();
// }
// }
// if(good[i]) {
// if(!q.empty()) {
// to[i] = q.front();
// }
// }
// }
// for(int i=0; i<N; ++i) {
// cerr<<good[i]<<' ';
// }
// cerr<<'\n';
// for(int i=0; i<N; ++i) if(good[i] && !tag[i]) {
// dfs(i);
// }
// if(ans==1e9) ans = -1;
// return ans;
}
