#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector< vector<int> > B) {
vector< vector<int> > occ(K);
for (int i = 0; i < M; i++) {
for (auto& x : B[i]) {
occ[x].push_back(i);
}
}
auto prev = [&](const int &x, const int &i) {
return ((x - i) % M + M) % M;
};
vector<int> cnt(M, 0);
for (int i = 0; i < M; i++) {
for (auto& x : occ[C[i]]) {
cnt[prev(x, i)]++;
}
}
vector<bool> a(N, false);
for (int i = 0; i < M; i++) {
if (cnt[i] == M) {
a[0] = true;
}
}
for (int i = M; i < N; i++) {
for (auto& x : occ[C[i - M]]) {
cnt[prev(x, i % M)]--;
}
for (auto& x : occ[C[i]]) {
if (++cnt[prev(x, i % M)] == M) {
a[i - M + 1] = true;
}
}
}
if (!a[N - M]) {
return -1;
}
vector<int> dp(N, INF);
dp[N - M] = 1;
multiset<int> st;
for (int i = 0; i < M - 1; i++) {
st.insert(INF);
}
st.insert(1);
for (int i = N - M - 1; i >= 0; i--) {
if (a[i]) {
dp[i] = min(dp[i], *st.begin() + 1);
}
st.erase(st.lower_bound(dp[i + M]));
st.insert(dp[i]);
}
if (dp[0] == INF) {
return -1;
}
return dp[0];
}
