#include <bits/stdc++.h>
using namespace std;
int minimumInstructions (int n, int m, int k, vector <int> c, vector <int> a, vector <vector <int>> b) {
vector <int> occ[k];
for (int i = 0; i < m; i++) {
for (auto j : b[i]) {
occ[j].push_back(i);
}
}
vector <bool> ok(n, 0);
vector <vector <int>> dp(n);
for (int i = n - 1; i >= 0; i--) {
dp[i].resize(occ[c[i]].size());
bool flag = 0;
for (int j = 0; j < (int)dp[i].size(); j++) {
dp[i][j] = 1;
int l = (occ[c[i]][j] + 1) % m;
if (i + 1 < n) {
auto z = lower_bound(occ[c[i + 1]].begin(), occ[c[i + 1]].end(), l) - occ[c[i + 1]].begin();
if (z != occ[c[i + 1]].size() && occ[c[i + 1]][z] == l) {
dp[i][j] += dp[i + 1][z];
}
}
flag |= dp[i][j] >= m;
}
ok[i] = flag;
}
vector <int> dp2(n);
multiset <int> cur;
for (int i = n - 1; i >= n - m; i--) {
dp2[i] = n + 1;
if (ok[i]) {
dp2[i] = 1;
}
cur.insert(dp2[i]);
}
for (int i = n - m - 1; i >= 0; i--) {
if (!ok[i]) {
dp2[i] = n + 1;
} else {
dp2[i] = 1 + (*(cur.begin()));
}
cur.erase(cur.lower_bound(dp2[i + m]));
cur.insert(dp2[i]);
}
return dp2[0] <= n ? dp2[0] : -1;
}
/*
int main () {
cout << minimumInstructions(8, 3, 5, {3, 3, 1, 3, 4, 4, 2, 2}, {3, 2, 2}, {{0, 1, 2}, {2, 3}, {3, 4}});
cout << minimumInstructions(5, 4, 4, {1, 0, 1, 2, 2}, {2, 1, 1, 1}, {{0, 1}, {1}, {2}, {3}});
}*/
