#include "paint.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <iomanip>
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC optimize("O3")
#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;
vector<unordered_set<ll>> like(k); // like[i] is a set of all those who like the color i
rep(i, 0, m) {
rep(j, 0, A[i]) {
like[B[i][j]].insert(i);
}
}
vvpll left(n);
for (auto& it : like[C[0]]) {
left[0].push_back({ it, 0 });
}
rep(i, 1, n) {
sort(left[i - 1].begin(), left[i - 1].end());
for (auto& it : like[C[i]]) {
ll last_color = (it - 1 + m) % m;
ll f = 0, t = left[i - 1].size() - 1;
ll idx = -1;
while (f <= t) {
//cout << "f = " << f << " t = " << t << endl;
ll mid = (f + t) / 2;
if (left[i - 1][mid].first > last_color) {
t = mid - 1;
}
else if (left[i - 1][mid].first < last_color) {
f = mid + 1;
}
else {
idx = mid;
break;
}
}
if (idx != -1) {
left[i].push_back({ it, left[i - 1][idx].second });
}
else {
left[i].push_back({ it, i });
}
/*
auto temp = lower_bound(left[i - 1].begin(), left[i - 1].end(), { last_color, 0 }, cmp);
if (temp != left[i - 1].end() && (*temp).first == last_color) {
left[i].push_back({ it, (*temp).second });
}
else {
left[i].push_back({ it, i });
}*/
}
}
vector<bool> possible(n, false);
rep(i, 0, n) {
if (left[i].empty()) continue;
for (auto& it : left[i]) {
ll l = it.second;
if (i - l + 1 >= m) {
possible[i] = true;
break;
}
}
}
ll cur_end = n - 1;
if (!possible[cur_end]) return -1;
ll ans = 1;
while (cur_end >= m) {
bool check = false;
rep(i, cur_end - m, cur_end) {
if (possible[i]) {
cur_end = i;
check = true;
ans++;
break;
}
}
if (!check) return -1;
}
if (!possible[m - 1]) return -1;
return ans;
rep(i, 0, n) {
cout << "i = " << i << endl;
for (auto& it : left[i]) {
cout << (it);
}
}
return 3;
}
/*
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
*/
