#include "paint.h"
#include <bits/stdc++.h>
int Ng;
std::vector<int> validCom[100010];
//list of valid company for i color;
std::vector<std::pair<int,int>> dp1[100010];
//for fence i there is increasing subsequence ending with p1 long p2
bool valid[100010];
//there is valid x and instruction for y=i
int dp2[100010];
//reversedminfenwick tree
int update(int min,int idx){
//idx = Ng-idx;
while(idx>0){
dp2[idx]=std::min(dp2[idx],min);
idx -= idx & -idx;
}
return 0;
}
int getmin(int idx){
//idx = Ng-idx;
int res = 1e9;
while(idx<=Ng){
res=std::min(res,dp2[idx]);
idx += idx & -idx;
}
return res;
}
int minimumInstructions(int N, int M, int K, std::vector<int> C,std::vector<int> A, std::vector<std::vector<int>> B) {
Ng=N;
for(int i=0;i<M;i++){
for(int j=0;j<A[i];j++){
validCom[B[i][j]].push_back(i);
//push the company to each their valid color
}
}
for(int i=0;i<K;i++){
std::sort(validCom[i].begin(),validCom[i].end());
//sort in case i need bs search later
}
for(int i=0;i<N;i++){
for(auto com:validCom[C[i]]){
dp1[i].push_back({com,1});
}
if(i!=0)
for(auto& [last,length]:dp1[i]){
std::pair<int,int> pp={last-1,1};
auto res = std::lower_bound(dp1[i-1].begin(),dp1[i-1].end(),pp);
//if(res!=dp1[i-1].end())
//std::cout << last << ',' << res->second << ' ';
if(res==dp1[i-1].end()||res->first!=last-1){
continue;
}
else{
length=1+res->second;
}
}
if(i>=M-1){
for(auto [last,length]:dp1[i]){
if(last==length-1){
if(length==M){
valid[i-M+1]=true;
}
else{
std::pair<int,int> pp={M-1,M-1-last};
auto itr = std::lower_bound(dp1[i-length].begin(),dp1[i-length].end(),pp);
if(itr!=dp1[i-length].end()&&itr->first==M-1){
valid[i-M+1]=true;
}
}
}
}
}
if(i>M){
dp1[i-M-1].clear();
}
//std::cout << '\n';
}
for(int i=M-1;i<N;i++){
}
// for(int i=0;i<N;i++){
// for(auto [last,length]:dp1[i]){
// std::cout << '{'<< last << ',' << length << '}' << ',';
// }
// std::cout << '\n';
// }
// for(int i=0;i<N;i++){
// if(valid[i])std::cout << 'T';
// else std::cout << 'N';
// }
for(int i=0;i<=N;i++){
dp2[i]=1e9;
}
for(int i=0;i<N;i++){
if(valid[i]){
int curr;
if(i!=0)
curr = getmin(i-1+1);
else curr=0;
update(curr+1,i+M-1+1);
}
}
// std::cout << '\n';
// for(int i=0;i<N;i++){
// std::cout << getmin(i+1) << ' ';
// }
int ans = getmin(N-1+1);
if(ans>=1e9)
return -1;
else
return getmin(N-1+1);
}
