#include "paint.h"
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <cmath>
using namespace std;
#define pb push_back
#define f first
#define s second
#define ll long long
const int maxn = 1e6 + 200, maxm = 1e3 + 200, inf = 1e9;
int n, m, k;
int is[maxn], dp[maxn], t[maxn * 4];
void upd(int pos, int val, int v = 1, int tl = 0, int tr = n - 1){
if (tl == tr){
t[v] = val;
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm)
upd(pos, val, v + v, tl, tm);
else
upd(pos, val, v + v + 1, tm + 1, tr);
t[v] = min(t[v + v], t[v + v + 1]);
}
int get(int l, int r, int v = 1, int tl = 0, int tr = n - 1){
if (l <= tl && tr <= r){
return t[v];
}
if (l > tr || r < tl)
return inf;
int tm = (tl + tr) / 2;
return min(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
}
vector<int> g[maxn];
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
n = N, m = M, k = K;
for (int i = 0; i < m; ++i){
for (auto it : B[i]){
g[it].pb(i);
}
}
for (int i = m - 1; i < n; ++i){
for (auto it : g[C[i]]){
int x = it;
int ok = 1;
int z = 0;
/* if (i == n - 1){
cout << x << '\n';
}*/
while (z < m){
int ok2 = 0;
for (auto it2 : B[x]){
if (C[i - z] == it2){
ok2 = 1;
break;
}
}
if (ok2 == 0){
ok = 0;
break;
}
x = (x - 1 + m) % m;
z += 1;
}
if (ok == 1){
is[i] = 1;
break;
}
}
}
for (int i = 0; i < n; ++i){
dp[i] = inf;
upd(i, dp[i]);
}
if (is[m - 1] > 0){
dp[m - 1] = 1;
upd(m - 1, 1);
}
for (int i = m; i < n; ++i){
if (is[i] > 0){
dp[i] = min(dp[i], get(i - m, i - 1) + 1);
}
upd(i, dp[i]);
}
if (dp[n - 1] == inf){
dp[n - 1] = -1;
}
return dp[n - 1];
}
