#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b){
vector<vector<int>> g(k);
for(int j = 0;j<m;j++){
for(auto x : b[j]){
g[x].push_back(j);
}
}
bool st[n];
memset(st, 0, sizeof st);
vector<int> dp(m, -1), dpn(m, -1);
for(int i = n - 1;i>=0;i--){
for(auto x : g[c[i]]){
int nx = (x + 1) % m;
if(i == n - 1 || dpn[nx] == -1) dp[x] = i;
else dp[x] = dpn[nx];
if(dp[x] >= i + m - 1) st[i] = 1;
}
if(i != n - 1) for(auto x : g[c[i + 1]]) dpn[x] = -1;
for(auto x : g[c[i]]) dpn[x] = dp[x];
swap(dpn, dp);
}
vector<int> l(n, -1);
int p = -1;
for(int i = 0;i<n;i++){
if(i <= n - m && st[i]) p = i;
l[i] = p;
}
int ans = 0, cur = 0;
while(cur < n){
if(l[cur] == -1 || l[cur] + m <= cur) return -1;
++ans;
cur = l[cur] + m;
}
return ans;
}
