#include "paint.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define ll long long
#define sz size()
using namespace std;
const int N=1e5+3;
int pref[N][633];
int dp[N],mx[N];
vector<int>pos[N];
int cnt_of[N];
int minimumInstructions(
int N, int M, int K, std::vector<int> C,
std::vector<int> A, std::vector<std::vector<int>> B) {
ios_base::sync_with_stdio(0);cin.tie(0);
for(int i=0;i<M;i++){
for(int j=0;j<A[i];j++){
pos[B[i][j]].push_back(i);
}
}
for(int i=0;i<N;i++){
mx[i]=0;
if(i==0||pos[C[i-1]].empty()){
for(int j=0;j<(int)pos[C[i]].sz;j++){
pref[i][j]=1;
mx[i]=1;
}
continue;
}
mx[i]=1;
int k=0;
for(int j=0;j<(int)pos[C[i]].sz;j++){
pref[i][j]=1;
int need=(pos[C[i]][j]-1+M)%M;
if(need==M-1){
if(pos[C[i-1]].back()==need){
pref[i][j]=pref[i-1][(int)pos[C[i-1]].sz-1]+1;
mx[i]=max(mx[i],pref[i][j]);
}
continue;
}
while(k<(int)pos[C[i-1]].sz&&pos[C[i-1]][k]<need)k++;
if(k==(int)pos[C[i-1]].sz||pos[C[i-1]][k]!=need)continue;
pref[i][j]=pref[i-1][k]+1;
mx[i]=max(mx[i],pref[i][j]);
}
}
multiset<int>st;
st.insert(0);
for(int i=0;i<M-1;i++){
dp[i]=1e9;
st.insert(dp[i]);
}
for(int i=M-1;i<N;i++){
dp[i]=1e9;
if(mx[i]>=M){
// cout<<*st.begin()<<"\n";
dp[i]=min(*st.begin()+1,dp[i]);
}
if(i-M==-1)st.erase(st.begin());
else st.erase(st.find(dp[i-M]));
st.insert(dp[i]);
}
// cout<<"mx :\n";
// for(int i=0;i<N;i++){
// // cout<<i<<": "<<dp[i]<<"\n";
// cout<<i<<": "<<mx[i]<<"\n";
// }
// cout<<"dp :\n";
// for(int i=0;i<N;i++){
// cout<<i<<": "<<dp[i]<<"\n";
// // cout<<i<<": "<<mx[i]<<"\n";
// }
return (dp[N-1]>=1e9?-1:dp[N-1]);
}
// int main() {
// int N, M, K;
// assert(3 == scanf("%d %d %d", &N, &M, &K));
//
// std::vector<int> C(N);
// for (int i = 0; i < N; ++i) {
// assert(1 == scanf("%d", &C[i]));
// }
//
// std::vector<int> A(M);
// std::vector<std::vector<int>> B(M);
// for (int i = 0; i < M; ++i) {
// assert(1 == scanf("%d", &A[i]));
// B[i].resize(A[i]);
// for (int j = 0; j < A[i]; ++j) {
// assert(1 == scanf("%d", &B[i][j]));
// }
// }
//
// int minimum_instructions = minimumInstructions(N, M, K, C, A, B);
// printf("%d\n", minimum_instructions);
//
// return 0;
// }
