#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;
vector<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);
}
}
vector<set<pll>> left(n);
for (auto& it : like[C[0]]) {
left[0].insert({ it, 0 });
}
rep(i, 1, n) {
for (auto& it : like[C[i]]) {
left[i].insert({ it, i });
ll last_color = (it - 1 + m) % m;
auto temp = left[i - 1].lower_bound({ last_color, 0 });
if (temp != left[i - 1].end() && (*temp).first == last_color) {
left[i].erase({ it, i });
left[i].insert({ it, (*temp).second });
}
}
}
vector<bool> possible(n, false);
rep(i, 0, n) {
if (left[i].empty()) continue;
if (i - (*prev(left[i].end())).second + 1 >= m) {
possible[i] = true;
}
}
ll cur_end = n - 1;
if (!possible[cur_end]) return -1;
ll ans = 1;
while (cur_end >= m) {
rep(i, cur_end - m, cur_end) {
if (possible[i]) {
cur_end = i;
ans++;
}
}
}
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
*/
