#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int inf = 3e5;
struct DS{
vector<int> a, f;
int n, mx;
DS(int ns){
n = ns;
a.resize(n + 1);
f.resize(n + 1);
f[0] = n;
mx = 0;
}
void upd(int p, int x){
p++;
if (x == 1){
f[a[p]]--;
a[p]++;
f[a[p]]++;
mx = max(mx, a[p]);
}
else {
if (a[p] == mx && f[a[p]] == 1) mx--;
f[a[p]]--;
a[p]--;
f[a[p]]++;
}
}
int get(){
return mx;
}
};
int minimumInstructions(int n, int m, int k, vector<int> x, vector<int> A, vector<vector<int>> B){
vector<int> d[k];
for (int i = 0; i < m; i++){
for (int j: B[i]){
d[j].pb(i);
}
}
vector<int> p(n + 1);
int i = 0, j = 0, j1 = 0;
DS T(inf);
while (i < n){
if (T.get() == (j1 - i)){
j = j1;
while (j < n){
for (int f: d[x[j]]){
T.upd(f - j + n, 1);
T.upd(f - j + (m + n), 1);
}
if (T.get() != (j - i + 1)){
j1++;
break;
}
j++; j1++;
}
if (i <= (j - m)){
p[i]++;
p[j - m + 1]--;
}
}
for (int f: d[x[i]]){
T.upd(f - i + n, -1);
T.upd(f - i + (m + n), -1);
}
i++;
}
vector<bool> gd(n);
int sum = 0;
for (int i = 0; i < n; i++){
sum += p[i];
gd[i] = (sum > 0);
}
int mx = -1, t = -1, out = 0;
for (int i = 0; i < n; i++){
if (gd[i]) t = i;
if (i == (mx + 1)){
if (t == -1) return -1;
mx = t + m - 1;
t = -1;
out++;
}
}
return out;
}
