#include "paint.h"
//Dost Seferoğlu
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e9;
const int N = 2e5;
bool has(const vi& v,int x) {
auto it = lower_bound(all(v),x);
if (it == v.end() || *it != x) return 0;
return 1;
}
int minimumInstructions(
int N, int M, int K, std::vector<int> C,
std::vector<int> A, std::vector<std::vector<int>> B) {
vector<int> f[K];
for (int i=0;i<M;i++) {
for (int j=0;j<A[i];j++) {
f[B[i][j]].push_back(i);
}
}
vector<bool> cool(N,0);
vi lst(M,0);
for (int i=N-1;i>=0;i--) {
vector<pii> ps;
for (auto j : f[C[i]]) {
if (i<N-1 && has(f[C[i+1]],(j+1)%M)) {
ps.push_back({j,min(M,lst[(j+1)%M]+1)});
}
else ps.push_back({j,1});
}
for (auto it : ps) {
if (it.ss == M) cool[i] = 1;
lst[it.ff] = it.ss;
}
}
int ans = 0;
int cover = -1;
stack<int> cools;
for (int i=0;i<N;i++) {
if (cool[i]) cools.push(i);
if (cover < i) {
if (cools.empty() || cools.top()+M-1 < i) {
ans = inf;
break;
}
else {
ans++;
cover = cools.top()+M-1;
cools.pop();
}
}
}
return ((ans >= inf)?-1:ans);
}
