#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
const int inf = 1e8;
const int mxN = 20505;
set<int> pos[100005];
int dp[mxN][2050], Good[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){
if((int) pos[C[i]].size() == 0) return -1;
}
SegmentTree tr(N + 1);
tr.update(0, 0, 0);
for(int i = 1; i <= N; ++i){
for(auto v : pos[C[i - 1]]){
dp[i][v] = dp[i - 1][v - 1] + 1;
}
}
for(int i = 1; i <= N; ++i){
if(i >= M){
int st = i - M + 1;
for(auto v : pos[C[st - 1]]){
int just = M - v;
if(dp[st + just - 1][M - 1] >= just && dp[i][M - just - 1] >= M - just) {
Good[i] = 1;
break;
}
}
}
}
for(int i = 1; i <= N; ++i){
if(i >= M && Good[i]){
tr.update(i - M + 1, i, tr.query(i - M) + 1);
}
}
int ans = tr.query(N);
return (ans >= inf ? -1 : ans);
}
