#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<vector<int>> F(K);
for (int i = 0; i < m; i++) {
for (auto j : B[i])
F[j].push_back(i);
}
vector<vector<bool>> dp1(n, vector<bool>(m)), dp2(n, vector<bool>(m)); //dp1: 0 ... x, dp2: x ... m - 1
for (int i = 0; i < n; i++) {
dp1[i][0] = (!F[C[i]].empty() && !F[C[i]][0]);
if (i) {
for (auto j : F[C[i]])
if (j) dp1[i][j] = dp1[i - 1][j - 1];
}
}
for (int i = n - 1; i >= 0; i--) {
dp2[i][m - 1] = (!F[C[i]].empty() && F[C[i]].back() == m - 1);
if (i != n - 1) {
for (auto j : F[C[i]])
if (j < m - 1) dp2[i][j] = dp2[i + 1][j + 1];
}
}
vector<int> dp(n, (int)1e9);
for (int i = m - 1; i < n; i++) {
int mn = (int)1e9;
for (int j = i - m; j < i; j++)
mn = min(mn, (~j ? dp[j] : 0));
if (mn == (int)1e9) continue;
bool tr = dp1[i][m - 1];
for (int j = 1; j < m && !tr; j++)
tr = (dp2[i - m + 1][j] && dp1[i][j - 1]);
if (tr) dp[i] = mn + 1;
}
return (dp[n - 1] == (int)1e9 ? -1 : dp[n - 1]);
}
