//#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
vector<int> st[N], lt[N];
vector<int> pre(N/2, -1);
vector<int> mx(N, -1e9);
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++){
st[b[i][j]].push_back(i);
}
}
for(int j : st[c[0]]){
pre[j] = 0;
lt[0].push_back(0);
}
for(int i=1; i<n; i++){
for(int j : st[c[i]]){
lt[i].push_back(pre[(j-1+m) % m] == -1 ? i : pre[(j-1+m) % m]);
}
for(int j : st[c[i-1]]) pre[j] = -1;
for(int j=0; j<st[c[i]].size(); j++) pre[st[c[i]][j]] = lt[i][j];
}
fill(pre.begin(), pre.end(), -1);
for(int j=0; j<st[c[n-1]].size(); j++){
pre[st[c[n-1]][j]] = n-1;
if(n-1 - lt[n-1][j] + 1 >= m) mx[n-1] = max(mx[n-1], n-1);
}
for(int i=n-2; i>=0; i--){
vector<int> rt;
for(int j=0; j<st[c[i]].size(); j++){
int val = pre[(st[c[i]][j]+1) % m] == -1 ? i : pre[(st[c[i]][j]+1) % m];
if(val - lt[i][j] + 1 >= m) mx[i] = max(mx[i], val);
rt.push_back(val);
}
for(int j : st[c[i+1]]) pre[j] = -1;
for(int j=0; j<st[c[i]].size(); j++) pre[st[c[i]][j]] = rt[j];
}
int ans = 0;
for(int i=0; i<n;){
if(mx[i] == -1e9) return -1;
i = min(i+m, mx[i]+1);
ans++;
}
return ans;
}
