#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const int MAXN = 1e5;
const int MAXM = 5e4;
const int MAXK = 1e5;
int N, M, K;
int C[MAXN+10], A[MAXM+10];
vector<int> B[MAXM+10];
vector<int> D[MAXK+10];
int dp[MAXN+10];
int P[MAXM+10];
int minimumInstructions(int _N, int _M, int _K, vector<int> _C, vector<int> _A, vector<vector<int>> _B)
{
N=_N; M=_M; K=_K;
for(int i=1; i<=N; i++) C[i]=_C[i-1];
for(int i=0; i<M; i++) A[i]=_A[i];
for(int i=0; i<M; i++) B[i]=_B[i];
for(int i=0; i<M; i++)
{
for(auto it : B[i])
{
D[it].push_back(i);
}
}
for(int i=1; i<=N; i++) if(D[C[i]].empty()) return -1;
for(int i=1; i<M; i++)
{
for(auto it : D[C[i]])
{
P[((it-i)%M+M)%M]++;
}
}
int cnt=0;
for(int i=0; i<M; i++) if(P[i]==M) cnt++;
deque<int> DQ;
for(int i=1; i<=N; i++) dp[i]=INF;
DQ.push_back(0); DQ.push_back(M-1);
for(int i=M; i<=N; i++)
{
if(i!=M) for(auto it : D[C[i-M]])
{
if(P[((it-i)%M+M)%M]==M) cnt--;
P[((it-i)%M+M)%M]--;
}
for(auto it : D[C[i]])
{
P[((it-i)%M+M)%M]++;
if(P[((it-i)%M+M)%M]==M) cnt++;
}
while(!DQ.empty() && DQ.front()<i-M) DQ.pop_front();
if(cnt && dp[DQ.front()]!=INF) dp[i]=dp[DQ.front()]+1;
while(!DQ.empty() && dp[DQ.back()]>=dp[i]) DQ.pop_back();
DQ.push_back(i);
}
if(dp[N]==INF) return -1;
else return dp[N];
}
