//GRT_2018
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
int minimumInstructions(int n, int m, int k, vi c, vi len, vector<vi>acceptable) {
vector<vi>who(k);
for(int i = 0; i < m; ++i) {
for(int ac : acceptable[i]) {
who[ac].PB(i);
}
}
vi dp((int)who[c[0]].size());
for(int &x : dp) x = 1;
vi state(n);
for(int &x : state) x = 0;
if(m == 1) state[0] = 1;
for(int i = 1; i < n; ++i) {
int ptr = 0;
vi new_dp((int)who[c[i]].size());
for(int &x : new_dp) x = 1;
int id = 0;
for(int j : who[c[i]]) {
while(ptr < (int)who[c[i - 1]].size() && who[c[i - 1]][ptr] < j - 1) {
ptr++;
}
if(ptr < (int)who[c[i - 1]].size() && who[c[i - 1]][ptr] == j - 1) {
new_dp[id] = dp[ptr] + 1;
}
if(j == 0 && (int)who[c[i - 1]].size() != 0 && who[c[i - 1]].back() == m - 1) {
new_dp[id] = dp.back() + 1;
}
id++;
}
int mx = -1;
for(int x : new_dp) mx = max(mx, x);
if(mx >= m) {
state[i] = 1;
}
dp.swap(new_dp);
}
vi S = {};
for(int i = 0; i < n; ++i) {
if(!state[i]) continue;
while((int)S.size() > 1 && S[(int)S.size() - 2] + m >= i) S.pop_back();
S.PB(i);
}
for(int i = 1; i < (int)S.size(); ++i) {
if(S[i - 1] + m < S[i]) {
return -1;
}
}
if(S.empty() || S.back() != n - 1) return -1;
return (int)S.size();
}
//int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//cout << minimumInstructions(8, 3, 5, {3, 3, 1, 3, 4, 4, 2, 2}, {3, 2, 2}, {{0, 1, 2}, {2, 3}, {3, 4}}) << "\n";
//cout << minimumInstructions(5, 4, 4, {1, 0, 1, 2, 2}, {2, 1, 1, 1}, {{0, 1}, {1}, {2}, {3}}) << "\n";
//}
