#include "paint.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <queue>
#include <stack>
#include <utility>
#include <array>
#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;
const ll MAX_N = 100000;
const ll MAX_M = 50005;
const ll MAX_K = 100000;
ostream& operator<<(ostream & os, const pll & p)
{
cout << "{" << p.first << ", " << p.second << "}" << endl;
return os;
}
vll like[MAX_K];
inline ll FAST_MOD(ll x, ll m) {
if (x < 0) return x + m;
return x;
}
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;
//vvll 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]].push_back(i);
}
}
//vvpll left(n);
vll possible(n, 0);
vpll next_left_arr;
vpll left_arr;
for (auto& it : like[C[0]]) {
left_arr.push_back({ it, 0 });
if (m == 1) {
possible[0] = 1;
}
}
rep(i, 1, n) {
sort(left_arr.begin(), left_arr.end());
for (auto& it : like[C[i]]) {
ll last_color = FAST_MOD(it - 1, m);
ll f = 0, t = left_arr.size() - 1, mid;
ll idx = -1;
while (f <= t) {
//cout << "f = " << f << " t = " << t << endl;
mid = (f + t) / 2;
if (left_arr[mid].first > last_color) {
t = mid - 1;
}
else if (left_arr[mid].first < last_color) {
f = mid + 1;
}
else {
idx = mid;
break;
}
}
if (idx != -1) {
next_left_arr.push_back({ it, left_arr[idx].second });
if (i - left_arr[idx].second + 1 >= m) {
possible[i] = 1;
}
}
else {
next_left_arr.push_back({ it, i });
if (i - left_arr[idx].second + 1 >= m) {
possible[i] = 1;
}
}
/*
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 });
}*/
}
left_arr.clear();
rep(i, 0, next_left_arr.size()) {
left_arr.push_back(next_left_arr[i]);
}
next_left_arr.clear();
}
ll cur_end = n - 1;
if (!possible[n - 1]) 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_arr[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
6 3 4
1 3 0 0 1 2
1 1
1 3
2 0 2
3 3 4
3 0 1
1 1
1 3
2 0 2
4 3 4
1 3 0 1
1 1
1 3
2 0 2
*/
