#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
using ll = long long;
#define REP(i,n) for (int i = 0; i < n; i++)
#define trav(a,x) for (auto &a : x)
#define all(x) (x).begin(), (x).end()
#define D(x) cerr << #x << ": " << x << endl;
const int MAX_K = 100001;
const int MAX_M = 50001;
const int MAX_N = MAX_K;
int n,m,k;
vi col_to_contr[MAX_K];
vi cols;
int counts[MAX_M];
int work;
bool able[MAX_N];
vi get_mods(int i) {
vi mods;
trav(contr, col_to_contr[cols[i]]) {
mods.push_back((contr-(i%m)+m)%m);
}
return mods;
}
void add_tile(int i) {
vi mods = get_mods(i);
trav (mod, mods) {
counts[mod]++;
if (counts[mod] == m) work++;
}
}
void remove_tile(int i) {
vi mods = get_mods(i);
trav (mod, mods) {
if (counts[mod] == m) work--;
counts[mod]--;
}
}
int dp_ans() {
vi dp(n, 1e9);
deque<pi> q;
if (able[0]) dp[0] = 1;
q.push_back({dp[0], 0});
for (int i = 1; i <= n-m; i++) {
// remove old
while (q.size() && q.front().second < i-m) q.pop_front();
if (able[i]) {
// get min
int minn = q.front().first;
dp[i] = minn+1;
}
// push new
while (q.size() && q.back().first >= dp[i]) q.pop_back();
q.push_back({dp[i], i});
}
if (dp[n-m] > n) return -1;
return dp[n-m];
}
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; k = K;
cols = C;
REP(i,m) {
REP(j,A[i]) {
col_to_contr[B[i][j]].push_back(i);
}
}
REP(i,m) add_tile(i);
if (work) able[0] = 1;
for (int i = 1; i <= n-m; i++) {
// move
remove_tile(i-1);
add_tile(i+m-1);
if (work) able[i] = 1;
}
/*D(n);
D(m);
REP(i, n-m) {
if (able[i]) cerr << "1";
else cerr << "0";
}
cerr << endl;*/
return dp_ans();
}
