#include<bits/stdc++.h>
#include "paint.h"
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
using namespace std;
int tr[1<<18]={0},n=100005;
vector<int> color[100002],possible1;
int Total[100002]={0};
int possible_place[100002]={0};
void modify(int p, int x) {
for(tr[p+=n] = x; p > 1; p>>=1)
tr[p>>1] = max(tr[p],tr[p^1]);
}
int query(int l, int r) { // [l,r)
int res = -1e9;
for(l+=n,r+=n; l<r; l>>=1,r>>=1) {
if(l&1) res = max(res, tr[l++]);
if(r&1) res = max(res, tr[--r]);
}
return res;
}
int cal_answer(int M,vector<int> possible){
if(!possible[M-1]) return -1;
int bound = M-1,answer = 1;
while(bound<(int)possible.size()-1){
int flag = 0;
for(int i=bound+M;i>bound;i--){
if(possible[i]){bound = i;answer +=1;flag = 1;break;}
}
if(!flag){answer = -1;break;}
}
return answer;
}
int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A, vector<vector<int>> B) {
for(int i=0;i<(int)B.size();i++){
for(int j=0;j<(int)B[i].size();j++){
color[B[i][j]].push_back(i);
}
}
for(int i=0;i<N;i++){
for(int j:color[C[i]]){
int active = (j + M - (i%M))%M;
Total[active]++;
modify(active+1,Total[active]);
}
if(i>=M){
for(int j:color[C[i-M]]){
int active = (j + M - (i%M))%M;
Total[active]--;
modify(active+1,Total[active]);
}
}
if(query(1,100001)==M) possible_place[i]=1;
}
for(int i=0;i<N;i++) possible1.push_back(possible_place[i]);
return cal_answer(M,possible1);
}
