#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#include <vector>
using ll = int;
const ll INF = 1e9;
struct Segment_Tree{
int sz = 1;
vector<int>tree;
Segment_Tree(int N){
while(sz < N)sz <<= 1;
tree.resize(sz * 2, INF);
}
#define left node * 2 + 1
#define right node * 2 + 2
void update(int idx, int val, int node, int l, int r){
if(l == r)return void(tree[node] = val);
int mid = l + r >> 1;
if(idx <= mid)update(idx, val, left, l, mid);
else update(idx, val, right, mid + 1, r);
tree[node] = min(tree[left], tree[right]);
}
void update(int idx, int val){
update(idx, val, 0, 0, sz - 1);
}
int query(int lq, int rq, int node, int l, int r){
if(l > rq || r < lq)return INF;
if(l >= lq && r <= rq)return tree[node];
int mid = l + r >> 1;
return min(query(lq, rq, left, l, mid), query(lq, rq, right, mid + 1, r));
}
int query(int lq, int rq){
return query(lq, rq, 0, 0, sz - 1);
}
#undef left
#undef right
};
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
vector<ll>dp(N, INF);
vector<vector<int>>comp(M, vector<int>(N));
vector<vector<int>>color(K);
for(int j = 0;j < M;j++){
for(auto x : B[j]){
color[x].push_back(j);
}
}
for(int i = 0;i < N;i++){
for(auto j : color[C[i]]){
comp[j][i] = 1;
}
}
auto check = [&](int x, int y){
bool ok = 1;
for(int i = 0;i < M;i++){
int xx = (x + i) % M;
int yy = y + i;
ok &= comp[xx][yy];
}
return ok;
};
Segment_Tree seg(N);
for(int i = M - 1;i < N;i++){
bool ok = 0;
for(int j = 0;j < M;j++){
ok |= check(j, i - M + 1);
if(ok)break;
}
if(!ok)continue;
if(i == M - 1){
dp[i] = 1;
}
int L = max(0, i - M);
ll Min = seg.query(L, i - 1);
dp[i] = min(dp[i] , Min + 1);
seg.update(i, dp[i]);
}
return (dp[N - 1] >= INF ? -1 : dp[N - 1]);
}
