#include <bits/stdc++.h>
#include "paint.h"
#pragma GCC target("sse,sse2,sse4,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 1e5+20,mod = 998244353,inf = 1e9+10;
inline int mkay(int a,int b){
if (a+b >= mod) return a+b-mod;
// if (a+b < 0) return a+b+mod;
return a+b;
}
inline int poww(int a,int k){
if (k < 0) return 0;
int z = 1;
while (k){
if (k&1) z = 1ll*z*a%mod;
a = 1ll*a*a%mod;
k >>= 1;
}
return z;
}
vector<int> f[N],a,c;
vector<vector<int> > b;
int n,m,k,dp[N];
vector<int> lst[N];
int minimumInstructions(int nn,int mm,int kk,vector<int> C,vector<int> A,vector<vector<int>> B){
n = nn;
m = mm;
k = kk;
c = C;
a = A;
b = B;
rep(i,0,m){
for (int x : b[i])
f[x].pb(i);
}
rep(i,0,n)
if (f[c[i]].empty()) return -1;
for(int x : f[c[n-1]]){
lst[n-1].pb(n-1);
}
dp[n-1] = n-1;
repr(i,n-2,0){
for (int x : f[c[i]]){
int y = x+1;
if (y == m) y = 0;
int ind = lower_bound(all(f[c[i+1]]),y)-f[c[i+1]].begin();
if (ind == (int)f[c[i+1]].size() || f[c[i+1]][ind] != y){
lst[i].pb(i);
dp[i] = max(dp[i],i);
continue;
}
int cal = lst[i+1][ind];
if (cal-i+1 > m) cal--;
lst[i].pb(cal);
dp[i] = max(dp[i],cal);
}
}
int ans = 0;
int cur = 0,rel = -1;
while (cur < n){
bool f = 0;
repr(i,cur,rel+1){
if(dp[i]-i+1 == m){
cur = i+m;
rel = i;
f = 1;
break;
}
}
if (!f) return -1;
ans++;
}
return ans;
}
