#include "paint.h"
#include <bits/stdc++.h>
int minimumInstructions(int N, int M, int K, std::vector<int> C,
std::vector<int> A, std::vector<std::vector<int>> B) {
// what can we do now
std::vector<std::vector<int>> colors(K);
for (int i = 0; i < M; i++) {
for (int j = 0; j < A[i]; j++) {
colors[B[i][j]].push_back(i);
}
}
std::vector<std::pair<int, int>> good;
for (int j = 0; j < (int) colors[C[N - 1]].size(); j++) {
good.emplace_back(colors[C[N - 1]][j], 1);
}
std::vector<int> ok(N);
ok[N - 1] = (colors[C[N - 1]].size() > 0) >= M;
for (int i = N - 2; i >= 0; i--) {
int r = 0;
std::vector<std::pair<int, int>> new_good;
int best = 0;
for (int l = 0; l < (int) colors[C[i]].size(); l++) {
while (r < (int) good.size() && good[r].first <= colors[C[i]][l]) {
r++;
}
if (r < (int) good.size() && good[r].first == colors[C[i]][l] + 1) {
best = std::max(best, good[r].second + 1);
new_good.emplace_back(colors[C[i]][l], good[r].second + 1);
} else {
if (l != (int) colors[C[i]].size() - 1) {
best = std::max(best, 1);
new_good.emplace_back(colors[C[i]][l], 1);
} else {
if (good.size() && good[0].first == 0 && colors[C[i]][l] == M - 1) {
best = std::max(best, good[0].second + 1);
new_good.emplace_back(colors[C[i]][l], good[0].second + 1);
} else {
best = std::max(best, 1);
new_good.emplace_back(colors[C[i]][l], 1);
}
}
}
}
std::swap(new_good, good);
ok[i] = best >= M;
}
const int inf = 1e9 + 7;
std::vector<int> dp(N + 1);
dp[N] = 0;
std::deque<int> dq;
dq.push_back(N);
for (int i = N - 1; i >= 0; i--) {
if (!ok[i]) {
dp[i] = inf;
} else {
while (dq.size() && dq.front() > i + M) dq.pop_front();
if (dq.size()) {
dp[i] = dp[dq.front()] + 1;
} else {
dp[i] = inf;
}
}
while (dq.size() && dp[dq.back()] >= dp[i]) {
dq.pop_back();
}
dq.push_back(i);
}
return dp[0] < inf ? dp[0] : -1;
}
