#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const int inf=1000000010;
const int mod=1000000007;
const int MAXN=100010;
int n, m, k, x, y, ans;
int C[MAXN];
int dp[MAXN], F[MAXN];
vector<int> col[MAXN];
bool ok[2000][20001];
inline int is_bad(int c, int ins){
return !ok[ins][c];
int pos=lower_bound(all(col[ins]), c)-col[ins].begin();
return (pos==col[ins].size() || col[ins][pos]!=c);
}
int minimumInstructions(int nn, int mm, int kk, vector<int> CC, vector<int> AA, vector<vector<int>> BB){
n=nn;
m=mm;
for (int i=0; i<n; i++) C[i]=CC[i], F[i]=i;
sort(all(CC));
CC.resize(unique(all(CC))-CC.begin());
k=min((int)CC.size()+1, kk);
for (int i=0; i<n; i++) C[i]=lower_bound(all(CC), C[i])-CC.begin();
for (int i=0; i<m; i++){
col[i].resize(AA[i]);
for (int j=0; j<AA[i]; j++){
int tmp=lower_bound(all(CC), BB[i][j])-CC.begin();
if (tmp==CC.size() || CC[tmp]!=BB[i][j]) col[i][j]=k-1;
else col[i][j]=tmp;
ok[i][col[i][j]]=1;
}
sort(all(col[i]));
}
for (int sh=0; sh<m; sh++){
int bad=0;
for (int i=0; i<n; i++){
bad+=is_bad(C[i], (i+sh)%m);
if (i>=m) bad-=is_bad(C[i-m], (i+sh)%m);
if (i>=m-1 && bad==0) F[i]=min(F[i], i-m), debug(i);
}
}
/*
for (int x=0; x<m; x++) for (int y=0; y<=n-m; y++){
bool bad=0;
for (int l=y; l<y+m && !bad; l++) if (is_bad(C[l], (x+l)%m)) bad=1;
if (bad) continue ;
F[y+m-1]=min(F[y+m-1], y-1);
debug2(y, y+m-1)
}
*/
for (int i=n-2; ~i; i--) F[i]=min(F[i], F[i+1]);
memset(dp, 63, sizeof(dp));
for (int i=0; i<n; i++) if (F[i]!=i){
if (F[i]==-1) dp[i]=1;
else dp[i]=dp[F[i]]+1;
}
if (dp[n-1]>n) return -1;
return dp[n-1];
}
/*
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4
*/
