#include <bits/stdc++.h>
#include "paint.h"
//#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
int minimumInstructions(int N, int M, int K,vector<int> C,vector<int> A, vector<vector<int>> B) {
vector <int> l(N),r(N),pr(N);
for(int i=0;i<N;i++){
int pos=i;
for(int j=0;j<min(M,N-i);j++){
auto it=lower_bound(all(B[j]),C[pos]);
if(it!=B[j].end() && *it==C[pos]){
pos++;r[i]++;
}
else break;
}
}
for(int i=N-1;i>=0;i--){
int pos=i;
for(int j=M-1;j>=max(0,M-i-1);j--){
auto it=lower_bound(all(B[j]),C[pos]);
if(it!=B[j].end() && *it==C[pos]){
pos--;l[i]++;
}
else break;
}
}
for(int i=0;i<N;i++){
int st1=i,st2=i-M+r[i];
if(i-1>=0)st1-=l[i-1];
if(st1<=st2){
pr[st1]++;
if(st2+1<N)pr[st2+1]--;
}
}
vector <int> v;
for(int i=0;i<N;i++){
if(i-1>=0)pr[i]+=pr[i-1];
if(pr[i]>0)v.pb(i);
}
int st=0,ans=0;
while(st!=N){
auto it=lower_bound(all(v),st);
if(it!=v.end() && *it==st){
st+=M;ans++;
}
else if(it!=v.begin()){
it--;
if(*it+M>st){
st=*it+M;ans++;
}
else {
ans=-1;break;
}
}
else{
ans=-1;break;
}
}
return ans;
}
/*signed main(){
ios_base::sync_with_stdio();
cin.tie(0);cout.tie(0);
int n,m,k;
cin>>n>>m>>k;
vector <int> c(n),a(m);
for(int i=0;i<n;i++)cin>>c[i];
for(int i=0;i<m;i++)cin>>a[i];
vector <vector <int> > b(m);
for(int i=0;i<m;i++){
for(int j=0;j<a[i];j++){
int x;
cin>>x;
b[i].pb(x);
}
}
cout<<minimumInstructions(n,m,k,c,a,b)<<"\n";
}*/
/*
8 3 5
3 3 1 3 4 4 2 2
3 2 2
0 1 2
2 3
3 4
5 4 4
1 0 1 2 2
2 1 1 1
0 1
1
2
3
*/
