#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
const int inf = 1e8;
const int mxN = 1e5 + 100;
set<int> pos[mxN], workers[mxN];
struct SegmentTree{
vector<int> seg, mx, lz;
int N;
SegmentTree(int n) : N(n) {
seg.resize(n * 4, inf);
mx.resize(n * 4, inf);
lz.resize(n * 4, inf);
}
void push(int node, int start, int end){
if(lz[node] == inf) return;
seg[node] = min(seg[node], lz[node]);
if(start ^ end){
lz[node * 2 + 1] = min(lz[node * 2 + 1], lz[node]);
lz[node * 2 + 2] = min(lz[node * 2 + 2], lz[node]);
}
lz[node] = inf;
}
void update(int node, int start, int end, int l, int r, int val){
push(node, start, end);
if(start > r || end < l || mx[node] <= val){
return;
}
if(start >= l && end <= r){
lz[node] = val;
push(node, start, end);
return;
}
int mid = start + (end - start) / 2;
update(node * 2 + 1, start, mid, l, r, val);
update(node * 2 + 2, mid + 1, end, l, r, val);
seg[node] = min(seg[node * 2 + 1], seg[node * 2 + 2]);
}
int query(int node, int start, int end, int idx){
push(node, start, end);
if(start == end) return seg[node];
int mid = start + (end - start) / 2;
if(idx <= mid) return query(node * 2 + 1, start, mid, idx);
else return query(node * 2 + 2, mid + 1, end, idx);
}
int query(int idx){
return query(0, 0, N, idx);
}
void update(int l, int r, int val){
return update(0, 0, N, l, r, 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(int j = 0; j < A[i]; ++j){
pos[B[i][j]].insert(i);
}
}
for(int i = 0; i < N; ++i){
for(auto v : pos[C[i]]) workers[v].insert(i);
if((int) pos[C[i]].size() == 0) return -1;
}
SegmentTree tr(N + 1);
tr.update(0, 0, 0);
auto fine_shyt = [&](int starting) -> bool {
for(auto st_id : pos[C[starting]]){
bool ok = 1;
for(int i = starting; i < starting + M; ++i){
int cur = ((st_id + i - starting) % M);
if(workers[cur].find(i) == workers[cur].end()){
ok = 0;
break;
}
}
if(ok) return 1;
}
return 0;
};
for(int i = 1; i <= N; ++i){
if(i >= M && fine_shyt(i - M)){
tr.update(i - M + 1, i, tr.query(i - M) + 1);
}
}
int ans = tr.query(N);
return (ans >= inf ? -1 : ans);
}
