#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<ll> vll;
typedef pair<ll , ll> ii;
typedef vector< ii > vii;
typedef pair < pair < ll , ll > , pair < ll , ll > > cm;
typedef tuple < int, ll, ll > tp;
#define ff first
#define ss second
#define pb push_back
#define in insert
#define mem(a , b) memset(a, b ,sizeof(a))
const ll N = 1e5 + 5;
ll last[N], p[N];
bool mark[N];
vector < ll > col[N];
int minimumInstructions(int n, int m, int k, vector<int> c,vector<int> a, vector<vector<int>> b) {
for(ll i = 0; i < m; i++){
for(ll j = 0; j < a[i]; j++){
col[b[i][j]].pb(i);
}
}
mem(last, 0);
mem(p, 0);
mem(mark, 0);
for(ll i = n-1; i >= 0; i--){
vector < ii > v;
ll mx = i;
for(auto u : col[c[i]]){
ll nxt = (u + 1)%m;
if(last[nxt] == i + 1) v.pb({u, p[nxt]});
else v.pb({u, i});
}
for(auto [u , val] : v){
last[u] = i;
p[u] = val;
mx = max(val, mx);
}
if(mx >= i + m - 1) mark[i] = 1;
}
if(!mark[0]) return -1;
ll st = 0, vis = 0, ans = 1;
while(st < n){
ll r = st + m;
if(r >= n) break;
ll l = max(vis + 1, st + 1);
ll c = -1;
for(ll i = r; i >= l; i--){
if(mark[i]){
c = i; break;
}
}
if(c == -1) return -1;
vis = r;
st = c;
ans++;
}
return ans;
}
