#include<bits/stdc++.h>
using namespace std ;
const int N = 2e4+5 ;
const int M = 2005 ;
const int K = 1e5+5 ;
int dp[N][M] , maxi[N] , dp1[N] ;
vector<int> color[K] ;
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) ;
}
for(int i=0 ; i<n ; i++){
if(color[c[i]].empty()) return -1 ; // testing
}
for(int i=0 ; i<n ; i++){
for(int j:color[c[i]]){
if(i) dp[i][j]=dp[i-1][(j-1+m)%m]+1 ;
else dp[i][j]=1 ;
maxi[i]=max(maxi[i],dp[i][j]) ;
}
}
memset(dp1,0x3f,sizeof(dp1)) ;
for(int i=m-1 ; i<n ; i++){
for(int j=m ; j<=maxi[i] ; j++){
if(i-j>=0) dp1[i]=min(dp1[i],dp1[i-j]+(j-1)/m+1) ;
else dp1[i]=min(dp1[i],(j-1)/m+1) ;
}
}
if(dp1[n-1]==0x3f3f3f3f) return -1 ;
return dp1[n-1] ;
}
/*
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 ;
}
*/
