#include "paint.h"
#include <vector>
#include <set>
#include <numeric>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define vi vector<int>
vector<int> adj;
vector<bool> vis;
vector<int> up;
bool ada[100005];
vector<int> col[100005];
unordered_map<int, int> check[100005];
vector<int> cntt;
int minimumInstructions(int N, int M, int K, vi C, vi A, vector<vi> B){
cntt.assign(K, 1);
for(int i = 0; i < M; i ++)
for(int j = 0; j < A[i]; j ++){
col[B[i][j]].push_back(i);
check[B[i][j]][i] = cntt[B[i][j]];
cntt[B[i][j]] ++;
}
up.resize(N);
int cnt = 0;
for(int i = 0; i < N; i ++){
cnt += col[C[i]].size();
up[i] = cnt - 1;
}
adj.assign(cnt, -1);
vis.assign(cnt, 0);
for(int i = 0; i < N - 1; i ++){
int gi = (i == 0 ? 0 : up[i - 1] + 1);
// for(int uwu = 0; uwu < M; uwu ++)
// cout << check[C[i + 1]][uwu] << " "; cout << endl;
for(int j : col[C[i]]){
int gt = check[C[i + 1]][(j + 1) % M];
// cout << gi << " " << gt << endl;
if(gt){
int gi2 = up[i] + gt;
adj[gi] = gi2;
// cout << gi << " -> " << gi2 << endl;
}
gi ++;
}
}
int tpnw = 0;
for(int i = 0; i < cnt; i ++){
if(up[tpnw] < i) tpnw ++;
if(vis[i]) continue;
int tp = tpnw;
if(ada[tp]) continue;
int len = 1;
for(int nw = i;;){
vis[nw] = 1;
if(adj[nw] != -1){
len ++;
nw = adj[nw];
}else break;
}
// cout << i << " " << tp << " " << len << endl;
for(int j = tp; j <= min(tp + len - M, N - 1); j ++)
ada[j] = true;
}
if(!ada[0]) return -1;
vector<int> pref(N);
for(int i = 0; i < N; i ++){
if(ada[i]) pref[i] = i;
else if(i == 0) pref[i] = 0;
else pref[i] = pref[i - 1];
}
int ans = 0; bool you = true;
for(int cr = 0;;){
ans ++;
int nx = cr + M;
if(nx == N) break;
int id = pref[nx];
if(id == cr){
you = false; break;
}
cr = id;
}
if(!you) return -1;
return ans;
}
