#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
namespace{
const ll maxn = 1e5+5;
const ll mod = 1e9+7;
const ll inf = 1ll<<60;
}
int minimumInstructions( int n, int m, int k, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
vector<pii> dp; // current dp, {pos, val}
vector<int> cols[k];
REP(i, m){
for (auto c:B[i]) cols[c].pb(i);
}
vector<int> starts;
RREP(i, n){
int ptr = 0;
vector<pii> tdp;
for (auto id:cols[C[i]]) tdp.pb({id, 1});
int mx = 0;
REP(j, SZ(tdp)){
mx = max(mx, 1);
while(ptr < SZ(dp) && dp[ptr].f <= tdp[j].f){
ptr++;
}
if (ptr < SZ(dp) && dp[ptr].f == tdp[j].f+1){
tdp[j].s = dp[ptr].s+1;
mx = max(mx, tdp[j].s);
}
if (tdp[j].f == m-1 && SZ(dp) && dp[0].f == 0){ // special case
tdp[j].s = dp[0].s+1;
mx = max(mx, tdp[j].s);
}
}
if (mx >= m){
starts.pb(i);
}
dp = tdp;
}
reverse(ALL(starts));
int r = -1, pos = 0, ans = 0;
REP(i, n){
if (r >= i) continue;
ans++;
while(pos < SZ(starts) && starts[pos] <= i){
r = starts[pos]+m-1;
pos++;
}
if (r < i) return -1;
}
return ans;
}
