#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ve vector
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>
int n, m;
int ans(int i, ve<int>& arr) {
if (i >= n) return 0;
if (i - arr[i] >= m) return INT_MIN;
return ans(arr[i]+m, arr) + 1;
}
int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
ve<ve<int>> dp(N, ve<int>(M));
ve<ve<bool>> valid(M, ve<bool>(K));
ve<bool> seg(N);
ve<int> best(N);
n = N; m = M;
for (int i=0; i<M; i++) {
for (auto j:B[i]) {
valid[i][j] = true;
}
}
for (int j=0; j<M; j++) {
if (valid[j][C[N-1]]) {dp[N-1][j] = 1;}
else {dp[N-1][j] = -1;}
}
for (int i=N-2; i>=0; i--) {
for (int j=0; j<M; j++) {
if (valid[j][C[i]]) {
if (dp[i+1][(j+1)%M] != -1) {
dp[i][j] = dp[i+1][(j+1)%M] + 1;
}
else {dp[i][j] = 1;}
} else {dp[i][j] = -1;}
}
}
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
if (dp[i][j] >= M) {
seg[i] = true;
break;
}
}
if (i == 0 && !seg[i]) {return -1;}
if (seg[i]) {best[i] = i;}
else {best[i] = best[i-1];}
}
int hi = ans(0, best);
if (hi <= 0) return -1;
return hi;
}
