#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define F first
#define S second
#define PB push_back
#define FOR(i, n) for (int i = 0; i < n; i++)
const int maxn = 1e5 + 10, INF = 1e9 + 7;
int block = 224; // sqrt(m)
int n, m, k, c[maxn], tree[maxn * 4];
bool good[maxn] = {0};
unordered_set<int> pos[maxn];
unordered_set<int> can_paint[maxn];
void merge(unordered_set<int> &a, unordered_set<int> &b, int d){
auto it = a.begin();
while (it != a.end()){
if (b.count((*it + d) % m) == 0) a.erase(it++);
else it++;
}
}
void update(int x, int v, int tl = 0, int tr = maxn, int i = 1){
if (tl > x || tr < x) return;
if (tl == tr){
tree[i] = v; return;
}
int tm = (tl + tr) / 2;
update(x, v, tl, tm, i * 2); update(x, v, tm + 1, tr, i * 2 + 1);
tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
}
int range(int l, int r, int tl = 0, int tr = maxn, int i = 1){
if (tl > r || tr < l) return INF;
if (l <= tl && tr <= r) return tree[i];
int tm = (tl + tr) / 2;
return min(range(l, r, tl, tm, i * 2),
range(l, r, tm + 1, tr, i * 2 + 1));
}
int minimumInstructions(int N, int M, int K,
vector<int> C, vector<int> A, vector<vector<int>> B){
n = N, m = M, k = K; block = min(block, m);
FOR(i, n) c[i] = C[i];
FOR(i, m){
FOR(j, A[i]) can_paint[B[i][j]].insert(i);
}
FOR(i, n){
for (auto x : can_paint[c[i]]) pos[i].insert(x);
for (int j = i + 1; j < min(n, i + block); j++){
merge(pos[i], can_paint[c[j]], j - i);
}
}
FOR(i, n - m + 1){
int cur = i + block;
while (cur + block - 1 < i + m){
merge(pos[i], pos[cur], cur - i);
cur += block;
}
while (cur < i + m){
merge(pos[i], can_paint[c[cur]], cur - i);
}
if (pos[i].size() > 0) good[i] = true;
}
// FOR(i, n) cout << good[i] << ' '; cout << endl;
if (!good[n - m]) return -1;
fill(tree, tree + maxn * 4, INF);
update(n - m, 1);
for (int i = n - m - 1; i >= 0; i--){
if (!good[i]) continue;
int best = range(i, i + m);
update(i, best + 1);
}
// FOR(i, n) cout << range(i, i) << ' '; cout << endl;
int re = range(0, 0);
return (re < INF ? re : -1);
}
