#include "bits/stdc++.h"
#include "paint.h"
// #include "grader.cpp"
using namespace std;
int minimumInstructions(
int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b) {
vector <int> v[k+1];
for(int i = 0; i < m; i++) {
for(auto j : b[i]) {
v[j].push_back(i);
}
}
vector <vector <int>> d(n+2, vector <int> (705, 0));
vector <int> ind0(n+1, -1);
unordered_map <int, int> dp, dp1;
for(int i = 0; i < (int)v[c[n-1]].size(); i++) {
int x = v[c[n-1]][i];
if(x == 0) ind0[n-1] = i;
dp[x] = 1;
}
for(int i = n-2; i >= 0; i--) {
for(int j = 0; j < (int)v[c[i]].size(); j++) {
int x = v[c[i]][j];
if(x == 0) ind0[i] = j;
d[i][j] = dp[x+1] + 1;
dp1[x] = dp[x+1] + 1;
}
dp = dp1;
dp1.clear();
// for(int j = 0; j < m; j++) {
// if(vis[j][c[i]] == true) d[i][j] = d[i+1][j+1] + 1;
// }
}
// for(int i = 0; i < n; i++) {
// cout << i << '\n';
// for(int j = 0; j < (int)v[c[i]].size(); j++) {
// int x = v[c[i]][j];
// cout << x << ' ' << d[i][j] << "\n";
// }
// }
vector <bool> e(n+1, 0);
for(int i = 0; i < n - m + 1; i++) {
for(int j = 0; j < (int)v[c[i]].size(); j++) {
int x = i + m - 1, y = i + m - v[c[i]][j];
if(!v[c[i]][j] and d[i][j] + i > x) e[i] = true;
if(ind0[y] == -1) continue;
if(d[i][j] + i >= y and d[y][ind0[y]] + y > x) e[i] = true;
}
// int x = i + m - 1, cnt = m-1;
// if(i + d[i][0] > x) e[i] = true;
// for(int j = i + 1; j <= x; j++) {
// if(j + d[j][0] > x and i + d[i][cnt] >= j) e[i] = true;
// cnt--;
// }
}
vector <int> v1;
for(int i = 0; i < n; i++) {
if(e[i]) v1.push_back(i);
}
if(!e[0]) return -1;
int ans = 1, y = 0;
while(y < n - m) {
bool tr = 0;
int t = upper_bound(v1.begin(), v1.end(), y + m) - v1.begin() - 1;
if(t < 0) return -1;
y = v1[t];
ans++;
}
return ans;
}
