#include<bits/stdc++.h>
using namespace std ;
const int N = 2e4+5 ; // 1e5+5
const int M = 2005 ; // 5e4+5
const int K = 1e5+5 ;
int t , dp[2][M] , maxi[N] , dp1[N] ;
vector<int> color[K] ;
set<int> st ;
int minimumInstructions(int n , int m , int k , vector<int> c , vector<int> a , vector<vector<int>> b){
for(int i=0 ; i<m ; i++){
for(int j=0 ; j<a[i] ; j++) color[b[i][j]].push_back(i) ;
}
memset(dp,0xc0,sizeof(dp)) ;
for(int i=n-1 ; i>=0 ; i--){
memset(dp[t],0xc0,sizeof(dp[t])) ;
for(int j:color[c[i]]){
dp[t][j]=max(dp[!t][(j+1)%m],i) ;
maxi[i]=max(maxi[i],dp[t][j]) ;
}
if(maxi[i]-i+1>=m) st.insert(i) ;
t=!t ;
}
int ri = 0 , cnt = 0 ;
while(ri<n){
auto it = st.upper_bound(ri) ;
if(it==st.begin()) return -1 ;
it-- ; cnt++ ;
if(*it+m<=ri) return -1 ;
ri = *it+m ;
}
return cnt ;
}
/*
int main(){
// cout << minimumInstructions(8, 3, 5, {3, 3, 1, 3, 4, 4, 2, 2}, {3, 2, 2}, {{0, 1, 2}, {2, 3}, {3, 4}}) << '\n' ;
// cout << minimumInstructions(5, 4, 4, {1, 0, 1, 2, 2}, {2, 1, 1, 1}, {{0, 1}, {1}, {2}, {3}}) << '\n' ;
// cout << minimumInstructions(11,5,10,{0,0,0,0,0,0,0,0,0,0,0},{2,2,2,2,2},{{0,5},{0,6},{0,7},{0,8},{0,9}}) << '\n' ;
return 0 ;
}
*/
