//chockolateman
#include<bits/stdc++.h>
using namespace std;
int n,m,dp[100005],c[100005];
map<int,bool> likes[100005];
bool test_end(int i)
{
int y = i - m + 1;
if(y <= 0)
return false;
for(int x = 0 ; x < m ; x++)
{
bool problem = false;
for(int l = 0 ; l < m ; l++)
{
int cur_x = (x+l)%m;
int cur_y = y+l;
if(!likes[cur_x][c[cur_y]])
{
problem = true;
break;
}
}
if(!problem)
return true;
}
return false;
}
int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B)
{
n = N;
m = M;
for(int i = N ; i >= 1 ; i--) //make it 1-indexed
c[i] = C[i-1];
for(int j = 0 ; j < M ; j++)
for(auto x : B[j])
likes[j][x] = true;
dp[0] = 0;
deque<int> avail;
avail.push_back(0);
for(int i = 1 ; i <= N ; i++)
{
dp[i] = -1;
if(avail.empty())
continue;
if(i >= M+1 && avail.front() == dp[i-M-1])
avail.pop_front();
if(!test_end(i))
continue;
dp[i] = avail.front() + 1;
while(avail.back() > dp[i])
avail.pop_back();
avail.push_back(dp[i]);
}
return dp[N];
}
