#include "paint.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin() , x.end()
const int N = 1e5 , K = 1e5;
bool valid[N+1];
int dp[N+1];
vector<int> f[K+1];
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 (auto j : B[i]) f[j].push_back(i);
}
for (int i = 0 ; i <= N - M ; i++){
for (auto k : f[C[i]]){
bool x =1;
int cur = k;
for (int j = i ; j < i + M ; j++){
x &= binary_search(all(f[C[j]]) , cur);
cur = (cur + 1)%M;
}
valid[i] |= x;
}
}
for (int i = 1 ; i <= N ; i++) dp[i] = 2e9;
multiset<int> st;
if (valid[0]) st.insert(0);
for (int i = 1 ; i <= N ; i++){
if (!st.empty()) dp[i] = *st.begin() + 1;
if (valid[i]) st.insert(dp[i]);
if (i >= M && valid[i-M]) st.erase(st.find(dp[i-M])) ;
}
return (dp[N] >= 2e9 ? -1 : dp[N]);
}
// dp[i] = min(dp[j]) for all j >= i - m and there
