// You can't change other people; you can only change yourself.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "paint.h"
// Pragmas
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// Namespaces
#define yume using
#define wo namespace
#define kanaeyo std
#define nazotte __gnu_pbds
yume wo kanaeyo;
yume wo nazotte;
// Data types
using i8 = __int128;
using ll = long long;
using si = short int;
using ld = long double;
// Pairs
using pi8 = pair<i8, i8>;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using psi = pair<si, si>;
using pld = pair<ld, ld>;
#define fi first
#define se second
// PBDS
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// Quick macro functions
#define sqr(x) ((x)*(x))
#define pow2(x) (1ll << (x))
#define debug(x) cout << #x << " = " << (x) << '\n'
#define debugV(x, a) cout << #x << "[" << (a) << "] = " << (x[a]) << '\n'
// Check min and max
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
// Modular arithmetic
template<typename T> void maddto(T &a, T b, T mod) {a += b; a %= mod;}
template<typename T> void msubto(T &a, T b, T mod) {a -= b; while (a < 0) a += mod; a %= mod;}
template<typename T> void mmulto(T &a, T b, T mod) {a *= b; a %= mod;}
template<typename T> T madd(T a, T b, T mod) {a += b; a %= mod; return a;}
template<typename T> T msub(T a, T b, T mod) {a -= b; while (a < 0) a += mod; return a;}
template<typename T> T mmul(T a, T b, T mod) {a *= b; a %= mod; return a;}
// Constants
const ll ModA = 998244353;
const ll ModC = 1e9 + 7;
const ll INF = 1e18;
const ll iINF = 1e9;
const ld EPS = 1e-9;
const ld iEPS = 1e-6;
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
vector<int> contractor[K];
for (int i = 0; i < M; i++) {
for (int j = 0; j < A[i]; j++) {
contractor[B[i][j]].push_back(i);
}
}
vector<bool> pos(N);
int len[2][N];
memset(len, 0, sizeof(len));
int first = (N-1) & 1;
vector<int> filled[2];
for (auto x : contractor[C[N-1]]) {
len[first][x] = 1;
filled[first].push_back(x);
if (len[first][x] >= M) {
pos[N-1] = 1;
}
}
for (int i = N-2; i >= 0; i--) {
int cur = i & 1, prv = cur ^ 1;
for (auto x : contractor[C[i]]) {
len[cur][x] = len[prv][(x+1) % M] + 1;
filled[cur].push_back(x);
if (len[cur][x] >= M) {
pos[i] = 1;
}
}
for (auto f : filled[prv]) {
len[prv][f] = 0;
}
filled[prv].clear();
}
vector<int> segments;
for (int i = 0; i < N; i++) {
if (pos[i]) {segments.push_back(i);}
}
segments.push_back(N);
vector<int> used = {-M};
for (auto s : segments) {
if (s > used.back() + M) {
return -1;
} else {
int us = used.size();
if (us >= 2 && s <= used[us-2] + M) {
used.pop_back();
}
used.push_back(s);
}
//for (auto i : used) {cout << i << ' ';}
//cout << '\n';
}
return used.size()-2;
}
//int main() {}
