#include <bits/stdc++.h>
using namespace std;
#define FOR(i,s,e) for(int i = s; i <= (int)e; ++i)
#define DEC(i,s,e) for(int i = s; i >= (int)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{" << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#define reach cerr << "LINE: " << __LINE__ << "\n";
#else
#define reach
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
typedef pair <int, int> pi;
typedef tuple<int,int,int> ti3;
typedef tuple<int,int,int,int> ti4;
int rand(int a, int b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (long long)1e18 + 500;
template <typename T> bool chmax(T& a, const T b) { return a<b ? a = b, 1 : 0; }
template <typename T> bool chmin(T& a, const T b) { return a>b ? a = b, 1 : 0; }
const int MAXN = 100005;
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,tune=native")
int D[MAXN];
unordered_map<int,int> dp[2];
int store[MAXN];
vector<int> V[MAXN]; // contractors of this colour
bool can[MAXN];
struct node {
int s,e,m,val;
node *l, *r;
node(int _s, int _e) {
s=_s;e=_e;
m=(s+e)/2;
val=inf;
if(s!=e) {
l=new node(s,m);
r=new node(m+1,e);
}
}
void update(int x, int nval) {
if(s==e) {
val=nval;
return;
}
if(x>m)r->update(x,nval);
else l->update(x,nval);
val=min(l->val,r->val);
}
int query(int x, int y) {
if(s==x&&e==y) return val;
if(x>m) return r->query(x,y);
else if(y<=m) return l->query(x,y);
else return min(l->query(x,m), r->query(m+1,y));
}
} *seg;
int minimumInstructions(
int n, int m, int k, std::vector<int> C,
std::vector<int> A, std::vector<std::vector<int>> B) {
seg=new node(0,n);
FOR(i,0,m-1) { // this contractor
int y=A[i];
FOR(j,0,y-1) { // V[i] -> the indices of contractors of this index.
V[B[i][j]].pb(i);
}
}
FOR(i,1,MAXN)D[i]=inf;
D[0]=0;
bool alt;
FOR(i,0,n-1) {
alt=i%2;
dp[alt].clear();
for(auto x:V[C[i]]) {
// index of contractor that can paint this place
// for continuous segment, all V values are the same
// store longest segment of this same value
int V=i-x;
chmax(dp[alt][V],dp[1-alt][V]+1);
}
db(i);
dbvp(dp[alt]);
store[i]=dp[alt][i-(m-1)];
//now check if i can cover from [i-m+1 to i]
int st=i-m+1;
if(st<0)continue;
for(auto x:dp[alt]) {
int idx=-(x.f-i); // idx of the contractor
int len=min(x.s,idx+1);
if(idx == m-1) {
if(len>=m){
can[i]=1;
break;
}
}
if(idx>=len)continue;
//idx<len
int curidx=i-len;
db(curidx);
if(curidx<0){
continue;
}
int req=m-len;
if(store[curidx]>=req){
can[i]=1;
break;
}
}
//actually after this, the only value that matters is the largest val
}
dba(store,0,n-1);
dba(can,0,n-1);
seg->update(0,0);
FOR(i,m,n) { // this is thing should be one indexed
if(!can[i-1])continue;
chmin(D[i], seg->query(i-m, i-1) + 1);
seg->update(i, D[i]);
}
if(D[n]>=inf)return -1;
else return D[n];
}
