#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i>=(k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
typedef long long ll;
const int INF = (int)1e9;
const ll INFF = (ll)1e18;
int minimumInstructions(
int n, int m, int k, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
vector<vector<int>> g(k); // which contractors like this color
REP(i, m){
for(int x : B[i]){
g[x].pb(i); // color x is liked by ith contractor too
}
}
vector<vector<int>> starts(m); // for this start as modulo, which ones are okay?
vector<bool> starts_valid(n, false); // does valid segment start here?
REP(i, n){
for(int off : g[C[i]]){
int start = (off - i);
start %= m;
if(start < 0) start += m;
starts[start].pb(i);
}
}
REP(i, m){
deque<int> dq; // if max - min == m - 1; ok
if(starts[i].size() < m)
continue;
REP(j, m){
dq.push_back(starts[i][j]);
if(dq.back() - dq[0] == m - 1){
starts_valid[dq[0]] = true;
}
}
FOR(j, m, starts[i].size(), 1){
dq.pop_front();
dq.push_back(starts[i][j]);
if(dq.back() - dq[0] == m - 1){
starts_valid[dq[0]] = true;
}
}
}
// I have all valid starts
vector<int> dp(n + 1, INF);
multiset<int> se;
se.insert(0);
se.insert(INF + 12); // this last one will not be erased
dp[0] = 0;
FOR(i, m, n + 1, 1){
if(!starts_valid[i - m]){
if(se.find(dp[i - m]) != se.end())
se.erase(se.find(dp[i - m]));
se.insert(dp[i]);
continue;
}
/*
FOR(j,i - m, i, 1){
dp[i] = min(dp[i], dp[j] + 1);
}
*/
dp[i] = *se.begin() + 1;
if(se.find(dp[i - m]) != se.end())
se.erase(se.find(dp[i - m]));
se.insert(dp[i]);
}
if(dp[n] >= INF){
return -1;
}
else{
return dp[n];
}
return 0;
}
