#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
bool ee[100005];
int rem[50005];
int minimumInstructions(
int N, int M, int K, std::vector<int> C,
std::vector<int> A, std::vector<std::vector<int>> B) {
memset(ee, false, sizeof(ee));
vector<vector<int>> allowed(K);
for (int i = 0; i < M; i ++) {
for (auto a : B[i])
allowed[a].push_back(i);
}
int bigmod = M;
while (bigmod <= N)
bigmod += M;
memset(rem, 0, sizeof(rem));
int goodcnt = 0;
for (int i = 0; i < N; i ++) {
for (auto a : allowed[C[i]]) {
int cc = (a - i + bigmod) % M;
rem[cc] ++;
if (rem[cc] == M)
goodcnt ++;
}
if (goodcnt > 0)
ee[i] = true;
else
ee[i] = false;
if (i >= M) {
// remove previous ones
for (auto a : allowed[C[i - M]]) {
int cc = (a - i + bigmod) % M;
if (rem[cc] == M)
goodcnt --;
rem[cc] --;
}
}
}
vector<int> dp(N + 1);
dp[0] = 0;
multiset<int> curmins;
curmins.insert(0);
for (int i = 1; i < M; i ++)
dp[i] = 1e9, curmins.insert(1e9);
for (int i = M; i <= N; i ++) {
int best = 1e9;
if (ee[i - 1]) {
best = min(best, *curmins.begin() + 1);
}
dp[i] = best;
curmins.erase(curmins.find(dp[i - M]));
curmins.insert(best);
}
// for (auto a : dp)
// cout << a << " "; cout << endl;
// for (int i = 0; i < N; i ++)
// cout << ee[i] << " "; cout << endl;
if (dp[N] == 1e9)
return -1;
return dp[N];
}
