#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = (int) 1e9 + 7;
int minimumInstructions(int n, int m, int k, vector<int> cwant, vector<int> cntt_t_, vector<vector<int>> like) {
vector<int> ok(n, 0);
assert((int) like.size() == m);
assert((int) cntt_t_.size() == m);
for (int i = 0; i < m; i++) {
assert((int) like[i].size() == cntt_t_[i]);
sort(like[i].begin(), like[i].end());
}
vector<int> cnt(m, 0);
function<int(int, int)> do_like = [&] (int i, int val) {
int l = 0, r = (int) like[i].size() - 1;
while (l <= r) {
int m = (l + r) / 2;
if (like[i][m] == val) {
return 1;
}
if (like[i][m] < val) {
l = m + 1;
} else {
r = m - 1;
}
}
return 0;
};
function<void(int, int)> add_position = [&] (int i, int sgn) {
for (int z = 0; z < m; z++) {
/*
0 -> z
1 -> (z + 1) % m
i -> (z + i) % m
*/
int guy = (z + i) % m;
if (do_like(guy, cwant[i])) {
cnt[z] += sgn;
}
}
};
for (int i = 0; i < m; i++) {
add_position(i, +1);
}
/*
ok[y][w] = 1 if wall y can be painted by worker w
eu vreau ok[y][x] & ok[y + 1][(x + 1) % n] & ... & ok[y + m - 1][(x + m - 1) % n]
dp[y][x] = longest cyclical thing starting here that works
*/
vector<bool> isok(n * m, 0);
vector<int> best(n * m, 0);
vector<bool> act(k, 0);
for (int w = 0; w < m; w++) {
for (auto &col : like[w]) {
act[col] = 1;
}
for (int i = 0; i < n; i++) {
if (act[cwant[i]]) {
isok[i * m + w] = 1;
}
}
for (auto &col : like[w]) {
act[col] = 0;
}
}
for (int i = n - 1; i >= 0; i--) {
for (int w = 0; w < m; w++) {
if (isok[i * m + w]) {
best[i * m + w] = 1;
if (i + 1 < n) {
best[i * m + w] += best[(i + 1) * m + (w + 1) % m];
}
}
}
}
for (int i = 0; i < m; i++) {
ok[0] |= (cnt[i] == m);
}
for (int l = 1; l <= n - m; l++) {
int r = l + m - 1;
add_position(r, +1);
add_position(l - 1, -1);
for (int i = 0; i < m; i++) {
ok[l] |= (cnt[i] == m);
}
}
for (int y = 0; y + m - 1 < n; y++) {
for (int w = 0; w < m; w++) {
if (best[y * m + w] >= m) {
//ok[y] = 1;
}
}
}
vector<int> inds;
for (int i = 0; i < n; i++) {
if (ok[i]) {
inds.push_back(i);
}
}
if (inds.empty()) {
return -1;
}
assert((int) inds.size() >= 1);
if (inds[0] != 0 || inds.back() != n - m) {
return -1;
}
int l = 0, cost = 0;
while (1) {
int r = l;
cost++;
while (r + 1 < (int) inds.size() && inds[r + 1] <= inds[l] + m) {
r++;
}
if (r == (int) inds.size() - 1) {
if (l < r) {
cost++;
}
break;
}
if (l == r) {
return -1;
}
l = r;
}
return cost;
}
