#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vb = vector<bool>;
using pll = pair<ll, ll>;
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define ef emplace_front
#define fst first
#define snd second
const int INF = 1e9;
int minimumInstructions(int N, int M, int K, vi C, vi A, vector<vi> B) {
vector<vi> where(K);
forn(i, M) forn(j, A[i]) where[B[i][j]].pb(i);
vi freq(M);
int good = 0;
vb can(N);
forn(y, N) {
for (int x : where[C[y]]) {
int d = (x - y) % M;
if (d < 0) d += M;
good -= freq[d] == M;
freq[d]++;
good += freq[d] == M;
}
if (y >= M) for (int x : where[C[y - M]]) {
int d = (x - y) % M;
if (d < 0) d += M;
good -= freq[d] == M;
freq[d]--;
good += freq[d] == M;
}
if (good > 0) {
assert(y >= M - 1);
can[y - (M - 1)] = true;
}
}
vi dp(N + 1, INF);
multiset<int> curr = {0, INF};
vector<vi> erase(N + 2);
erase[1].pb(0);
forn(x, N + 1) {
for (int v : erase[x]) curr.erase(curr.find(v));
dp[x] = *curr.begin();
if (x < N && can[x]) {
curr.insert(dp[x] + 1);
erase[x + M + 1].pb(dp[x] + 1);
}
}
if (dp[N] == INF) return -1;
return dp[N];
}
