#include "paint.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int mxn = 1e5+10;
#define pii pair<int,int>
#define fs first
#define sc second
set<int> col[mxn];
bitset<mxn> able;
int N,M,K;
int arr[mxn];
bool check(int s){
bool re = false;
for(auto i:col[arr[s]]){
int now = s;
bool f = true;
for(int j = 0;j<M;j++){
if(col[arr[now]].find(i) == col[arr[now]].end()){
f = false;
break;
}
now++;
i = (i+1)%M;
}
if(f)re = true;
}
return re;
}
namespace GRAPH{
vector<int> paths[mxn];
int dist[mxn];
queue<int> q;
void bfs(int s){
memset(dist,-1,sizeof(dist));
q.push(s);
dist[s] = 0;
while(!q.empty()){
auto now = q.front();
q.pop();
for(auto nxt:paths[now]){
if(dist[nxt] == -1){
dist[nxt] = dist[now]+1;
q.push(nxt);
}
}
}
return;
}
int GO(){
for(int i = 0;i<N;i++){
if(able[i]){
for(int j = 1;j<=M;j++)paths[i].push_back(i+j);
}
}
bfs(0);
return dist[N];
}
}
int minimumInstructions(
int NN, int MM, int K, std::vector<int> C,
std::vector<int> A, std::vector<std::vector<int>> B) {
N = NN,M = MM;
for(int i = 0;i<M;i++){
for(int j = 0;j<A[i];j++)col[B[i][j]].insert(i);
}
for(int i = 0;i<N;i++)arr[i] = C[i];
for(int i = 0;i+M<=N;i++)able[i] = check(i);
return GRAPH::GO();
}
