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