#include "paint.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = 2e4+9,MX = 1e9+9;
int n,m,k;
int a[inf];
vector<int> Cont[inf],Colors[inf];
int LCS[inf][2009],dp[inf];
bool valid[inf];
unordered_map<int,int> mp[inf];
int solve(int i,int j){
if( !(j>=1 && j<=m && i>=1 && i<=n) )
return 0;
int &ret = LCS[i][j];
if(ret != -1)
return ret;
ret = 0;
int idx=0;
/*if(!Cont[j].empty() ){
idx = lower_bound(Cont[j].begin(),Cont[j].end(),a[i])-Cont[j].begin();
if(idx < Cont[j].size() && Cont[j][idx] == a[i])
ret = 1 + solve(i+1,j+1);
}*/
if(mp[j][a[i]])
ret = 1 + solve(i+1,j+1);
return ret;
}
int minimumInstructions(int N, int M, int K, vector<int> C,
vector<int> A,vector<vector<int>> B) {
n = N, m = M,k = K;
for(int i=1;i<=n;i++)
a[i] = C[i-1]+1;
for(int i=1;i<=m;i++)
for(auto o:B[i-1])
/*Cont[i].push_back(o+1),Colors[o+1].push_back(i),*/mp[i][o+1] = 1;
for(int i=1;i<=m;i++)
if(!Cont[i].empty())
sort(Cont[i].begin(),Cont[i].end());
for(int i=1;i<=k;i++)
if(!Colors[i].empty())
sort(Colors[i].begin(),Colors[i].end());
memset(LCS,-1,sizeof(LCS));
for(int y=1;y <= n-m+1;y++){
for(int x = 1;x <= m;x++){
int len1 = m-x+1,i1 = y,j1 = x,tmp1;
tmp1 = solve(i1,j1);
int len2 = x-1,i2 = y+len1,j2 = 1,tmp2 = 0;
if(len2)
tmp2 = solve(i2,j2);
valid[y] |= (tmp1 >= len1 && tmp2 >= len2);
}
}
for(int i=1;i<=n;i++)
dp[i] = MX;
dp[n-m+1] = (valid[n-m+1]?1:MX);
for(int i=n-m;i>=1;i--)
for(int j=i+1;j<=i+m && valid[i];j++)
dp[i] = min(dp[i],dp[j] + 1);
return ( (dp[1] == MX)?-1:dp[1]);
}
