#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);
}
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);
}
}
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;
}
