#include "paint.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ft first
using namespace std;
using namespace __gnu_pbds;
const int M = 50100;
const int N = 100100;
const int K = 100100;
const int oo = 2e9;
gp_hash_table<int, bool> inside[K];
int f[N], cnt[M];
// проверить, вдруг на большие ограничения залетит
int minimumInstructions(int n, int m, int k, std::vector<int> C,
std::vector<int> A, std::vector<std::vector<int>> B) {
for (int i = 0; i < m; i++)
for (int j = 0; j < A[i]; j++)
inside[B[i][j]][i] = 1;
int ptr = 0;
for (int i = n - 1; i > n - m; i--){
for (auto cr : inside[C[i]]){
int loc = (ptr + cr.ft);
if (loc >= m)
loc -= m;
cnt[loc]++;
}
ptr++;
if (ptr == m) ptr = 0;
}
f[n] = 0;
fill(f, f + n, oo);
for (int i = n - m; i >= 0; i--){
int mn = oo;
for (int j = 1; j <= m; j++)
mn = min(mn, f[i + j]);
if (mn == oo) continue;
if (i + m < n){
for (auto cr : inside[C[i + m]]){
int loc = (ptr + cr.ft);
if (loc >= m)
loc -= m;
cnt[loc]--;
}
}
bool ok = 0;
for (auto cr : inside[C[i]]){
int loc = (ptr + cr.ft);
if (loc >= m)
loc -= m;
cnt[loc]++;
if (cnt[loc] == m) ok = 1;
}
if (ok) f[i] = mn + 1;
ptr++;
if (ptr == m) ptr = 0;
// for (auto cr : inside[C[i]]){
// int now = cr.ft;
// bool ok = 1;
//
// for (int it = 1; it < m && ok; it++){
// now++;
//
// if (now == m) now = 0;
//
// if (inside[C[i + it]].find(now) == inside[now].end()){
// ok = 0;
// break;
// }
// }
//
// if (ok){
// f[i] = mn + 1;
// break;
// }
// }
}
return (f[0] == oo ? -1 : f[0]);
}
