#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> II;
const int maxn = 1e5 + 5, logN = 20;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
int n, m, k, c[maxn], ok[maxn];
vector<int> g[maxn], f[maxn];
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 ++){
for(int j = 0; j < A[i]; j ++){
g[B[i][j]].push_back(i);
}
}
for(int i = 1; i <= n; i ++){
f[i].resize(g[c[i]].size());
int p = 0;
for(int j = 0; j < (int)f[i].size(); j ++){
f[i][j] = 1;
if(i != 1 && !g[c[i - 1]].empty()){
int pos = g[c[i]][j];
if(pos == 0){
int pp = lower_bound(g[c[i - 1]].begin(), g[c[i - 1]].end(), (pos - 1 + m) % m) - g[c[i - 1]].begin();
if(g[c[i - 1]][pp] == (pos - 1 + m) % m) f[i][j] += f[i - 1][pp];
}
else{
while(p + 1 < (int)g[c[i - 1]].size() && g[c[i - 1]][p + 1] <= pos - 1) p ++;
if(g[c[i - 1]][p] == pos - 1) f[i][j] += f[i - 1][p];
}
}
if(f[i][j] >= m) ok[i - m + 1] = true;
}
}
if(!ok[1]) return -1;
int cur = m, res = 1;
while(cur < n){
bool flag = false;
for(int i = cur + 1; i > cur - m + 1; i --){
if(ok[i]){
res ++;
cur = i + m - 1;
flag = true;
break;
}
}
if(!flag) return -1;
}
return res;
}
/*
int main(){
ios_base::sync_with_stdio(false);
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}}) << endl;
return 0;
}
*/
