#include <bits/stdc++.h>
using namespace std;
using vint = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pint = pair<int, int>;
using vpint = vector<pint>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using pill = pair<int, ll>;
using vpill = vector<pill>;
using plli = pair<ll, int>;
using vplli = vector<plli>;
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = (n)-1; i >= 0; --i)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a)-1; i >= (b); --i)
int minimumInstructions(int N, int M, int K, vint C, vint A, vector<vint> B) {
vector<vint> f(K);
rep(i, M) rep(j, A[i]) f[B[i][j]].push_back(i);
vpint vd_rl; vd_rl.reserve(N);
vint prff, nprff, prffv(N, -1);
rrep(i, N) {
nprff.clear(); prff.push_back(i); prffv[i] = i;
for (auto& v: f[C[i]]) {
if (0 <= i+M-1-v && i+M-1-v < N && prffv[i+M-1-v] == i) {
nprff.push_back(i+M-1-v);
prffv[i+M-1-v] = i-1;
}
}
swap(prff, nprff);
for (auto& v: nprff) if (i < v && prffv[v] != i-1)
vd_rl.push_back({i+1, v});
}
for (auto& v: prff) vd_rl.push_back({0, v});
vint idx; idx.reserve(N);
vint suff, suffv(N, -1); fill(all(prffv), -1);
int prff_i = sz(vd_rl)-1;
rep(i, N) {
suffv[i] = i;
for (auto& v: f[C[i]]) {
if (0 <= i-v && i-v < N && suffv[i-v] == i) {
suff.push_back(i-v);
suffv[i-v] = i+1;
}
}
nprff.clear();
for (auto& v: prff) {
if (i < M-1 || v >= i-M+1) nprff.push_back(v), prffv[v] = i+1;
}
while (prff_i >= 0 && vd_rl[prff_i].fi <= i-M+1) {
nprff.push_back(vd_rl[prff_i].se);
prffv[vd_rl[prff_i].se] = i+1;
prff_i--;
}
swap(prff, nprff);
if (i >= M-1) {
for (auto& v: suff) {
if (v == i-M+1 || prffv[v-1] == i+1) {idx.push_back(i-M+1); break;}
}
if (prffv[i] == i+1) if (sz(idx) == 0 || idx[sz(idx)-1] != i-M+1) idx.push_back(i-M+1);
}
suff.clear();
}
if (sz(idx) == 0) return -1;
int res = 0;
int cv = -1;
for(int i = 0; i < sz(idx);) {
int j = i;
while (j+1 < sz(idx) && idx[j+1] <= cv+1) j++;
if (idx[j] > cv+1) return -1;
cv = idx[j]+M-1;
i = j+1;
res++;
}
if (cv < N-1) return -1;
return res;
}
