#include "paint.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <iomanip>
#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmax(a, b) a = max(a, b)
#define upmin(a, b) a = min(a, b)
using namespace std;
using ll = int;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
const ll INF = 2e18;
const ll MOD = 1e9 + 7;
ostream& operator<<(ostream & os, const pll & p)
{
cout << "{" << p.first << ", " << p.second << "}" << endl;
return os;
}
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
ll n = N, m = M, k = K;
vll like(k, -1); // Every color has at most one person who likes it
rep(i, 0, m) {
rep(j, 0, A[i]) {
like[B[i][j]] = i;
}
}
queue<pair<pll, ll>> q; // {Start Point, Current End Point, Current Constructor}
rep(i, 0, n - m + 1) {
q.push({ {i, i}, {like[C[i]]} });
/*rep(j, 0, m) {
bool check = false;
auto it = lower_bound(B[j].begin(), B[j].end(), C[i]);
if (it != B[j].end() && *it == C[i]) check = true;
if (!check) continue;
q.push({ { i, i }, j });
}*/
}
vpll segments;
while (!q.empty()) {
ll cur_start = q.front().first.first;
ll cur_end = q.front().first.second;
ll cur_c = q.front().second; // Current constructor
q.pop();
bool check = false;
auto it = lower_bound(B[cur_c].begin(), B[cur_c].end(), C[cur_end]);
if (it != B[cur_c].end() && *it == C[cur_end]) {
check = true;
}
if (!check) continue;
ll next_c = (cur_c + 1) % m;
if (cur_end - cur_start + 1 == m) {
segments.push_back({ cur_start, cur_end });
}
else {
q.push({ {cur_start, cur_end + 1}, next_c });
}
}
/*rep(i, 0, segments.size()) {
cout << segments[i];
}*/
vll arr;
rep(i, 0, segments.size()) {
arr.push_back(segments[i].first);
}
sort(arr.begin(), arr.end());
ll idx = 0;
ll max_start = -1;
ll cur_end = -1;
ll ans = 0;
rep(i, 0, n) {
while (idx < arr.size()) {
if (arr[idx] != i) {
break;
}
upmax(max_start, arr[idx]);
idx++;
}
if (i == cur_end + 1) {
cur_end = max_start + m - 1;
ans++;
if (cur_end < i) {
return -1;
}
}
}
return ans;
}
/*
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4
5 4 4
1 0 1 2 2
2 0 1
1 1
1 2
1 3
*/
