#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
namespace{
const int inf=1e9;
}
int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> sz, vector<vector<int>> a) {
vector<vector<int>> con(k);
for(int i=0;i<m;i++){
for(int j=0;j<sz[i];j++){
con[a[i][j]].pb(i);
}
}
vector<int> mp(m);
auto f=[&](int v1, int v2){
int tep=v2-v1;
tep%=m;
if(tep<0) tep+=m;
return tep;
};
vector<bool> good(n);
int cnt=0;
auto add=[&](int tar){
mp[tar]++;
if(mp[tar]==m){
cnt++;
}
};
auto rem=[&](int tar){
if(mp[tar]==m) cnt--;
mp[tar]--;
};
for(int i=0;i<m;i++){
for(auto &it:con[c[i]]){
add(f(it, i));
}
}
if(cnt>0){
good[0]=1;
}
for(int i=1;i<=n-m;i++){
for(auto &it:con[c[i-1]]){
rem(f(it, i-1));
}
for(auto &it:con[c[i+m-1]]){
add(f(it, i+m-1));
}
if(cnt>0){
good[i]=1;
}
}
vector<int> dp(n-m+1, inf);
multiset<int> st;
if(!good[0]){
return -1;
}
dp[0]=1;
st.insert(dp[0]);
for(int i=1;i<=n-m;i++){
if(i-m-1>=0) st.erase(st.find(dp[i-m-1]));
if(!good[i]){
st.insert(dp[i]);
continue;
}
dp[i]=min(dp[i], (*st.begin())+1);
st.insert(dp[i]);
}
if(dp[n-m]==inf){
return -1;
}
return dp[n-m];
}
