#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++){
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)) ;
dp1[0]=0 ;
for(int i=1 ; i<=n ; i++){
if(maxi[i]<m) continue ;
dp1[i]=min(dp1[i-maxi[i]/m*m]+maxi[i]/m,dp1[i-maxi[i]]+maxi[i]/m+1) ;
}
/*
for(int i=0 ; i<n ; i++){
for(int j=0 ; j<m ; j++) cout << dp[i][j] << ' ' ;
cout << '\n' ;
}
for(int i=0 ; i<n ; i++) cout << maxi[i] << ' ' ; cout << '\n' ;
for(int i=0 ; i<n ; i++) cout << dp1[i] << ' ' ; cout << '\n' ;
*/
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' ;
return 0 ;
}
*/
