#include <bits/stdc++.h>
#define sz(v) (int)(v).size()
using namespace std;
const int MXn = 100005;
vector<int> arr1[MXn], arr2[MXn], nxt[MXn];
int prf[MXn];
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 c: B[i]) arr1[c].emplace_back(i);
}
for (int i = 0; i < N; i++) {
arr2[i] = arr1[C[i]];
nxt[i].resize(sz(arr2[i]));
}
for (int j = 0; j < sz(nxt[N - 1]); j++) nxt[N - 1][j] = N - 1;
for (int i = N - 2; i >= 0; i--) {
for (int j = 0; j < sz(nxt[i]); j++) {
nxt[i][j] = i;
int p = lower_bound(begin(arr2[i + 1]), end(arr2[i + 1]), (arr2[i][j] + 1) % M) - arr2[i + 1].begin();
if (p < sz(arr2[i + 1]) && arr2[i + 1][p] == ((arr2[i][j] + 1) % M)) {
nxt[i][j] = min(i + M - 1, nxt[i + 1][p]);
}
}
}
for (int i = 0; i <= N - M; i++) {
int able = 0;
for (int j = 0; j < sz(nxt[i]); j++) {
if (nxt[i][j] == i + M - 1) {
able = 1;
break;
}
}
prf[i] = able;
if (i > 0) prf[i] += prf[i - 1];
}
int ans = -1;
if (prf[0]) {
int tmp = 1;
int cur = 0;
while (cur < N - M) {
int l = cur + 1, r = min(cur + M, N - M), mid, pos;
int num = prf[r] - prf[l - 1];
if (!num) tmp = -N;
while (l <= r) {
mid = (l + r) >> 1;
if (prf[mid] - prf[cur] == num) {
pos = mid;
r = mid - 1;
} else l = mid + 1;
}
tmp++;
cur = pos;
}
ans = max(ans, tmp);
}
return ans;
}
