#include<bits/stdc++.h>
#include "paint.h"
using namespace std;
const int INF = 1e9;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
int minimumInstructions(int n, int m, int k, vector<int>c, vector<int>a, vector<vector<int>>b){
bool is_sub1 = true;
auto pre_check = [&] (){
vector<int>cnt(k, 0);
for(int i = 0; i < m; i++){
for(int& j : b[i]){
if(cnt[j]++ == 1){
is_sub1 = false;
return;
}
}
}
};
pre_check();
if(is_sub1){
vector<int>to(k, -2);
for(int i = 0; i < m; i++){
for(int& j : b[i]){
to[j] = i;
}
}
int cnt = 1, ans = 0, pre = to[c[0]];
for(int i = 1; i < n; i++, cnt++){
if(cnt == m){
cnt = 0;
if((pre = to[c[i]]) == -2){
return -1;
}
ans++;
}
else if(to[c[i]] != (pre = (pre + 1) % m)){
return -1;
}
}
return ans + 1;
}
if(n <= 20000 && m <= 2000 && false){
vector<vector<int>>p(k);
for(int i = 0; i < n; i++){
p[c[i]].emplace_back(i);
}
vector<vector<bool>>can(m, vector<bool>(n, false));
for(int i = 0; i < m; i++){
for(int& j : b[i]){
for(int& k : p[j]){
can[i][k] = true;
}
}
}
vector<bool>paint(n, false);
for(int i = 0; i + m <= n; i++){
for(int j = 0; j < m; j++){
bool flag = true;
for(int k = 0; k < m; k++){
if(!can[(j + k) % m][i + k]){
flag = false;
break;
}
}
if(flag){
paint[i] = true;
break;
}
}
}
vector<int>dp(n + 1, INF);
dp[n] = 0;
for(int i = n - 1; i > -1; dp[i--]++){
for(int j = min(i, n - m); j >= max(0, i - m + 1); j--){
if(paint[j]){
for(int k = i; k < j + m; k++){
minimize(dp[i], dp[k + 1]);
}
break;
}
}
}
return dp[0] >= INF ? -1 : dp[0];
}
vector<vector<int>>ins(k);
for(int i = 0; i < m; i++){
for(int& j : b[i]){
ins[j].emplace_back(i);
}
}
vector<int>f(n, 0);
vector<pair<int, int>>state;
for(int& i : ins[c[0]]){
state.emplace_back(i, 1);
}
f[0] = int(!state.empty());
for(int i = 1; i < n; i++){
vector<pair<int, int>>nxt_state;
for(int& j : ins[c[i]]){
nxt_state.emplace_back(j, 1);
}
if(!nxt_state.empty()){
nxt_state.emplace_back(nxt_state[0]);
nxt_state.back().first += m;
int ptr = 0;
for(auto& [p, v] : state){
while(nxt_state[ptr].first <= p){
ptr++;
}
if(nxt_state[ptr].first == p + 1){
nxt_state[ptr].second = v + 1;
}
}
maximize(nxt_state[0].second, nxt_state.back().second);
nxt_state.pop_back();
}
swap(state, nxt_state);
for(auto& [foo, v] : state){
maximize(f[i], v);
}
}
vector<bool>paint(n, false);
for(int i = 0; i < n; i++){
if(f[i] >= m){
paint[i - m + 1] = true;
}
}
vector<int>dp(n + 1, INF);
dp[n] = 0;
for(int i = n - 1; i > -1; dp[i--]++){
for(int j = min(i, n - m); j >= max(0, i - m + 1); j--){
if(paint[j]){
for(int k = i; k < j + m; k++){
minimize(dp[i], dp[k + 1]);
}
break;
}
}
}
return dp[0] >= INF ? -1 : dp[0];
}
