#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
int sz, T[N];
void build(int n){
sz=n;
for(int i = 0; i <= 2*sz+2; ++i) T[i] = 0;
}
void add(int v, int x){
++v;
v += sz;
T[v] += x;
for(v >>= 1; v; v >>= 1) T[v] = max(T[v<<1], T[v<<1|1]);
}
int minimumInstructions(int n, int m, int k, std::vector<int> CC, std::vector<int> A, std::vector<std::vector<int>> B) {
vector<vi> COL(k);
for(int i = 0; i < m; ++i){
for(int j = 0; j < A[i]; ++j) COL[B[i][j]].pb(i);
}
int C = m;
// int D = m;
build(C);
for(int j = 0; j + 1 < m; ++j){
for(int pos: COL[CC[j]]) add((j-pos+C)%C, 1);
}
vector<bool> ok(n);
for(int i = 0; i <= n - m; ++i){
for(int pos: COL[CC[i + m - 1]]) add((i+m-1-pos+C)%C, 1);
// cerr << T[1] << ' ';
if(T[1] == m){
ok[i] = 1;
}
for(int pos: COL[CC[i]]) add((i-pos+C)%C, -1);
}
if(ok[0] == 0 || ok[n-m] == 0) return -1;
vector<pii> P;
P.pb({0, 1});
int last = 0;
for(int i = 1; i <= n-m; ++i){
if(ok[i]) last = i;
if(last <= i - m) return -1;
if(ok[i]){
int pos = lower_bound(all(P), pii{i - m, -1}) - P.begin();
P.pb({i, P[pos].ss + 1});
}
// cerr << dp[i] << ' ';
}
return P.back().ss;
}
