#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
#define sz(x) (int)(x).size()
int minimumInstructions(int n, int m, int k, vi c, vi a, vector<vi> b) {
vector<vector<int>> DP(n);
vector<bool> F(n, false);
vector<vector<int>> val(k);
// build val[color] = list of positions in [0..m-1]
for (int i = 0; i < m; ++i) {
for (int x : b[i]) {
val[x].pb(i);
}
}
// base case i = n-1
DP[n-1].resize(sz(val[c[n-1]]), 1);
if (m == 1) F[n-1] = true;
// DP from right to left
for (int i = n - 2; i >= 0; --i) {
DP[i].resize(sz(val[c[i]]));
int best = 0;
int ptr = 0;
for (int idx = 0; idx < sz(val[c[i]]); ++idx) {
int j = val[c[i]][idx];
int need = (j + 1) % m;
while (ptr < sz(val[c[i + 1]]) && val[c[i + 1]][ptr] < need)
++ptr;
if (ptr == sz(val[c[i + 1]]) || val[c[i + 1]][ptr] != need) {
DP[i][idx] = 1;
} else {
DP[i][idx] = DP[i + 1][ptr] + 1;
}
best = max(best, DP[i][idx]);
}
if (best >= m) F[i] = true;
}
// greedy cover
int ans = 0;
int l = 0, r = 0;
while (r < n) {
bool ok = false;
while (r >= l) {
if (F[r]) {
++ans;
l = r + 1;
r = r + m;
ok = true;
break;
}
--r;
}
if (!ok) return -1;
}
return ans;
}
