#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
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>> inds(k);
for(int i = 0; i < m; i++)
for(int x : b[i])
inds[x].push_back(i);
for(int i = 0; i < k; i++)
reverse(inds[i].begin(), inds[i].end());
vector<pair<int, int>> last(m, make_pair(-2, 0));
vector<int> kezd(n, 0), veg(n, 0);
for(int i = 0; i < n; i++){
for(int x : inds[c[i]]){
if(x > 0 && last[x-1].first == i-1)
last[x] = make_pair(i, last[x-1].second+1);
else
last[x] = make_pair(i, 1);
}
/*for(auto p : last)
cout<<"("<<p.first<<", "<<p.second<<") ";
cout<<"\n";*/
if(last[m-1].first == i)
veg[i] = last[m-1].second;
}
for(int i = 0; i < k; i++)
reverse(inds[i].begin(), inds[i].end());
last.assign(m, make_pair(n+1, 0));
for(int i = n-1; i >= 0; i--){
for(int x : inds[c[i]]){
if(x < n-1 && last[x+1].first == i+1)
last[x] = make_pair(i, last[x+1].second+1);
else
last[x] = make_pair(i, 1);
}
if(last[0].first == i)
kezd[i] = last[0].second;
}
/*cout<<"veg: ";
for(int x : veg)
cout<<x<<" ";
cout<<"\n";
cout<<"kezd: ";
for(int x : kezd)
cout<<x<<" ";
cout<<"\n";*/
vector<pair<int, int>> v;
for(int i = 0; i < n; i++){
if(i < n-1 && veg[i] + kezd[i+1] >= m){
v.emplace_back(i-veg[i]+1, i + kezd[i+1] - m + 1);
} else if(veg[i] == m)
v.emplace_back(i-veg[i]+1, i-veg[i]+1);
}
/*cout<<"ints:\n";
for(auto p : v)
cout<<p.first<<" "<<p.second<<"\n";*/
sort(v.begin(), v.end());
int x = 0, e = 0, legn = -m-1, meg = 0;
while(e < n){
while(x < (int)v.size() && v[x].first <= e)
legn = max(legn, v[x++].second);
if(legn+m <= e)
return -1;
e = min(e+m, legn+m);
meg++;
}
return meg;
}
