#include "paint.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
const int MAXN = 1e5 + 5;
struct ST{
int tree[MAXN << 2];
ST(){
memset(tree, 63, sizeof tree);
}
void sett(int i, int v, int lx = 0, int rx = MAXN, int x = 1){
if(lx == rx) { tree[x] = v; return; }
int m = (lx + rx) >> 1;
if(i <= m) sett(i, v, lx, m, x<<1);
else sett(i, v, m+1, rx, x<<1|1);
tree[x] = min(tree[x<<1], tree[x<<1|1]);
}
int get(int l, int r, int lx = 0, int rx = MAXN, int x = 1){
if(lx > r || rx < l) return 1e9;
if(lx >= l && rx <= r) return tree[x];
int m = (lx + rx) >> 1;
return min(get(l, r, lx, m, x<<1), get(l, r, m+1, rx, x<<1|1));
}
}tree;
int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b){
vector<vector<int>> rev(k + 1);
for(int i=0;i<m;i++){
for(int j=0;j<a[i];j++){
rev[b[i][j]].push_back(i);
}
}
vector<vector<int>> dp(n + 1);
vector<int> is(n+1);
for(int i=0;i<n;i++){
int r = 0, l = 0, sz = rev[c[i]].size();
dp[i+1].resize(sz, 1);
for(auto x : rev[(i ? c[i-1] : k)]){
while(r < sz && rev[c[i]][r] <= x) r++;
if(r < sz && rev[c[i]][r] == x + 1){
dp[i+1][r] = dp[i][l] + 1;
if(dp[i+1][r] >= m){
is[i+1] = 1;
}
} l++;
}
if(!rev[c[i]].empty() && !rev[(i ? c[i-1] : k)].empty() && !rev[c[i]][0] && rev[c[i-1]].back() == m - 1){
dp[i+1][0] = dp[i].back() + 1;
if(dp[i+1][0] >= m) is[i+1] = 1;
}
}
vector<int> tp(n + 1, 1e9);
tree.sett(0, 0);
for(int i=1;i<=n;i++){
if(is[i]){
tp[i] = min(tp[i], tree.get(i - m, i - 1) + 1);
tree.sett(i, tp[i]);
}
}
//~ for(int i=1;i<=n;i++) cout<<tree.get(i, i)<<" ";
//~ cout<<"\n";
//~ for(int i=1;i<=n;i++) cout<<is[i]<<" ";
//~ cout<<"\n";
//~ for(int i=1;i<=n;i++) cout<<tp[i]<<" ";
//~ cout<<"\n";
if(tp[n] == 1e9) return -1;
else return tp[n];
}
/*
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4
5 4 4
1 0 1 2 2
2 0 1
1 1
1 2
1 3
*/
