#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int minimumInstructions(
int N, int M, int K, vector<int> C,
vector<int> A, vector<vector<int>> B) {
vector<vector<int>> D(K);
for (int i=0;i<M;i++){
for (int j=0;j<(int)B[i].size();j++){
D[B[i][j]].push_back(i);
}
}
vector<pair<int, int>> v, tmp;
vector<bool> chk(N);
for (int i=0;i<N;i++){
vector<bool> visited(D[C[i]].size());
for (auto &p:v){
if (p.second>=M) chk[i-M] = 1;
int tmp2 = p.first+1;
if (tmp2==M) tmp2 = 0;
auto iter = lower_bound(D[C[i]].begin(), D[C[i]].end(), tmp2);
if (iter!=D[C[i]].end() && *iter==tmp2){
tmp.emplace_back(tmp2, p.second+1);
visited[iter-D[C[i]].begin()] = 1;
}
}
if (i<=N-M+1){
for (int j=0;j<(int)D[C[i]].size();j++) if (!visited[j]){
tmp.emplace_back(D[C[i]][j], 1);
}}
swap(v, tmp);
tmp.clear();
/*printf("%d: ", i);
for (auto &p:v) printf("(%d, %d) ", p.first, p.second);
printf("\n");*/
}
for (auto &p:v) if (p.second>=M) chk[N-M] = 1;
//for (int i=0;i<N;i++) printf("%d ", (int)chk[i]);
//printf("\n");
int prv = 0, nxt = -1, cur = 0, cnt = 0;
while(prv<N){
bool flag = 0;
for (int i=cur;i<=prv;i++) if (chk[i]){
nxt = i+M;
flag = 1;
}
if (!flag) break;
cnt++;
cur = prv+1;
prv = nxt;
}
if (prv<N) return -1;
return cnt;
}
