#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int nax = 1e5 + 1;
vector<int> col_to_wall[nax], cand[nax];
bool good[nax];
int dp[2][700];
int minimumInstructions(
int N, int M, int K, vector<int> C,
vector<int> A, vector<vector<int>> B) {
for(int i=0; i<N; ++i) {
col_to_wall[C[i]].push_back(i);
}
for(int i=0; i<M; ++i) {
for(int j=0; j<A[i]; ++j) {
for(int x : col_to_wall[B[i][j]]) {
cand[x].push_back(i);
}
}
}
for(int i=0; i<K; ++i) {
col_to_wall[i].clear();
}
int rw = 0;
for(int i=N-1; i>=1; --i, rw = 1-rw) {
if(cand[i].empty()) {
memset(dp[rw], 0, sizeof dp[rw]);
continue;
}
int ptr = 0;
int sz2 = cand[i].size();
for(int j=0, sz=cand[i-1].size(); j<sz; ++j) {
dp[rw][j] = 0;
if(cand[i-1][j]+1==M) {
if(cand[i][0]==0) {
dp[rw][j] = 1 + dp[1-rw][0];
}
if(i-1<=N-M) {
if(dp[rw][j]+1>=M) good[i-1] = 1;
}
continue;
}
while(ptr+1<sz2 && cand[i][ptr+1]<=cand[i-1][j]+1) {
++ptr;
}
if(cand[i][ptr]==cand[i-1][j]+1) {
dp[rw][j] = 1 + dp[1-rw][ptr];
}
if(i-1<=N-M) {
if(dp[rw][j]+1>=M) good[i-1] = 1;
}
}
}
if(M==1 && !cand[N-1].empty()) good[N-1] = 1;
if(!good[0]) return -1;
int last = 0, pending = -1;
int ans = 1;
for(int i=1; i<N; ++i) {
if(good[i]) {
pending = i;
}
if(last+M==i) {
if(pending==-1) return -1;
last = pending;
pending = -1;
++ans;
}
}
return ans;
}
