#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);
vector<int> cnt(m, 0);
vector<vector<int>> who(k);
for (int guy = 0; guy < m; guy++) {
for (auto &lk : like[guy]) {
who[lk].push_back(guy);
}
}
int cm = 0;
function<void(int, int)> add_position = [&] (int i, int sgn) {
for (auto &guy : who[cwant[i]]) {
int z = (i + m - guy) % m;
cm -= (cnt[z] == m);
cnt[z] += sgn;
cm += (cnt[z] == m);
}
};
for (int i = 0; i < m; i++) {
add_position(i, +1);
}
ok[0] = (cm >= 1);
for (int l = 1; l <= n - m; l++) {
int r = l + m - 1;
add_position(r, +1);
add_position(l - 1, -1);
ok[l] = (cm >= 1);
}
vector<int> inds;
for (int i = 0; i < n; i++) {
if (ok[i]) {
inds.push_back(i);
}
}
if (inds.empty()) {
return -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;
}
