#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 20;
vector<vector<int>> good;
vector<vector<int>> streak;
vector<int> best_streak;
vector<int> dp;
vector<int> bit;
int N;
void update(int pos, int val) {
for (int i = pos; i <= N; i += i & (-i)) {
bit[i] = min(bit[i], val);
}
}
int get(int pos) {
int res = inf;
for (int i = pos; i > 0; i -= i & (-i)) {
res = min(res, bit[i]);
}
return res;
}
int minimumInstructions(int _N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
N = _N;
bit.resize(N + 1, inf);
good.resize(K);
for (int i = 0; i < M; i++) {
for (auto color: B[i]) {
good[color].push_back(i);
}
}
streak.resize(N);
best_streak.resize(N);
streak[N - 1].resize(good[C[N - 1]].size(), 1);
for (int i = N - 2; i >= 0; i--) {
streak[i].resize(good[C[i]].size(), 1);
int pt = 0;
for (int j = 0; j < (int)good[C[i]].size(); j++) {
while (pt < (int)good[C[i + 1]].size() && good[C[i + 1]][pt] < good[C[i]][j] + 1) {
pt++;
}
if (pt < (int)good[C[i + 1]].size() && good[C[i + 1]][pt] == good[C[i]][j] + 1) {
streak[i][j] = streak[i + 1][pt] + 1;
}
if (good[C[i]][j] == M - 1) {
if (!good[C[i + 1]].empty() && good[C[i + 1]][0] == 0) {
streak[i][j] = streak[i + 1][0] + 1;
}
}
}
}
for (int i = 0; i < N; i++) {
best_streak[i] = 0;
for (auto val: streak[i]) {
best_streak[i] = max(best_streak[i], val);
}
}
dp.resize(N);
for (int i = N - 1; i >= 0; i--) {
dp[i] = inf;
if (best_streak[i] >= M) {
if (i + M + 1 > N) {
dp[i] = 1;
}
else {
dp[i] = min(dp[i], get(i + M + 1) + 1);
}
}
update(i + 1, dp[i]);
}
if (dp[0] == inf) {
return -1;
}
else {
return dp[0];
}
}
