#include "paint.h"
// author: yanybayev
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
int minimumInstructions( int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
const int INF = 1e9 + 7;
vector<int> dp(M, INF);
vector<int> far(N, INF);
vector<vector<int>> g(K, vector<int>());
vector<pair<int, int>> prev;
vector<pair<int, int>> cur;
for (int i = 0; i < M; ++ i) for (int j = 0; j < A[i]; ++ j) g[B[i][j]].pb(i);
for (int i = 0; i < N; ++ i) {
for (auto it : g[C[i]]) {
if (dp[(it - 1 + M) % M] != INF) cur.pb({it, dp[(it - 1 + M) % M]});
else cur.pb({it, i});
far[i] = min(far[i], cur.back().ss);
}
for (auto it : prev) dp[it.ff] = INF;
for (auto it : cur) dp[it.ff] = it.ss;
prev = cur;
cur.clear();
}
int L = M - 1, R = M - 1, ANS = 0;
while (L < N) {
for (int i = R; i >= L; -- i) {
if (far[i] <= i - M + 1) {
L = i + 1;
R = i + M;
ANS += 1;
}
if (i == L) return -1;
}
}
return ANS;
}
