#include "paint.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
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);
}
}
for (int i=0;i<K;i++) sort(D[i].begin(), D[i].end());
vector<pair<int, int>> v, tmp;
vector<bool> chk(N);
for (int i=0;i<N;i++){
if (D[C[i]].empty()){
swap(v, tmp); tmp.clear();
continue;
}
if (v.empty()){
for (auto &x:D[C[i]]) v.emplace_back(x, 1);
continue;
}
int pt1 = 0, pt2 = 0;
for (auto &p:v){
if (p.second>=M) chk[i-M] = 1;
p.first++, p.second++;
}
if (v.back().first==M && !D[C[i]][0]){
tmp.emplace_back(0, v.back().second);
pt2++;
}
while(pt1<(int)v.size() && pt2<(int)D[C[i]].size()){
if (v[pt1].first==D[C[i]][pt2]){
tmp.push_back(v[pt1]);
pt1++, pt2++; continue;
}
if (v[pt1].first<D[C[i]][pt2]) pt1++;
else{
tmp.emplace_back(D[C[i]][pt2], 1);
pt2++;
}
}
for (;pt2<(int)D[C[i]].size();pt2++) tmp.emplace_back(D[C[i]][pt2], 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;
}
