#include "bits/stdc++.h"
#include "paint.h"
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int INF = 1e9 + 5;
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
int n = N,m = M,k = K;
int ar[n+5];
for(int i=1;i<=n;i++) ar[i] = C[i - 1];
vector<int> v[2*m+5];
for(int i=1;i<=m;i++){
for(int j = 0; j < A[i - 1]; j++){
int val = B[i - 1][j];
v[i].push_back(val);
v[i+m].push_back(val);
}
}
auto Query = [&](int ind,int val){
int it = lower_bound(all(v[ind]),val) - v[ind].begin();
if(it != sz(v[ind]) && v[ind][it] == val) return 1;
return 0;
};
int doable[n+5],dp[n+5];
memset(doable,0,sizeof(doable));
for(int i=m;i<=n;i++){
for(int j = 1; j <= m; j++){
int p = j;
int r = j + m - 1;
while(p <= r && Query(p,ar[i-m+1+p-j])) p++;
if(p > r){
doable[i] = 1;
break;
}
}
}
for(int i=1;i<=n;i++) dp[i] = INF;
dp[0] = 0;
deque<array<int,2>> dq;
dq.push_back({0, 0});
for(int i=1;i<=n;i++){
if(doable[i] == 1){
while(!dq.empty() && i - dq.front()[0] > m) dq.pop_front();
if(!dq.empty() && dq.front()[1] != INF) dp[i] = dq.front()[1] + 1;
}
while(!dq.empty() && dq.back()[1] >= dp[i]) dq.pop_back();
dq.push_back({i, dp[i]});
}
if(dp[n] == INF) return -1;
else return dp[n];
}
/*void _(){
int n,m,k;
cin >> n >> m >> k;
int ar[n+5];
for(int i=1;i<=n;i++) cin >> ar[i];
vector<int> v[2*m+5];
for(int i=1;i<=m;i++){
int u; cin >> u;
for(int j = 0; j < u; j++){
int val; cin >> val;
v[i].push_back(val);
v[i+m].push_back(val);
}
}
auto Query = [&](int ind,int val){
int it = lower_bound(all(v[ind]),val) - v[ind].begin();
if(it != sz(v[ind]) && v[ind][it] == val) return 1;
return 0;
};
int doable[n+5],dp[n+5];
memset(doable,0,sizeof(doable));
for(int i=m;i<=n;i++){
for(int j = 1; j <= m; j++){
int p = j;
int r = j + m - 1;
while(p <= r && Query(p,ar[i-m+1+p-j])) p++;
if(p > r){
doable[i] = 1;
break;
}
}
}
for(int i=1;i<=n;i++) dp[i] = INF;
dp[0] = 0;
deque<array<int,2>> dq;
dq.push_back({0, 0});
for(int i=1;i<=n;i++){
if(doable[i] == 1){
while(!dq.empty() && i - dq.front()[0] > m) dq.pop_front();
if(!dq.empty() && dq.front()[1] != INF) dp[i] = dq.front()[1] + 1;
}
while(!dq.empty() && dq.back()[1] >= dp[i]) dq.pop_back();
dq.push_back({i, dp[i]});
}
if(dp[n] == INF) cout << -1 << '\n';
else cout << dp[n] << '\n';
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/
