#include "paint.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int INF = 1e9;
int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
// [y,y+M-1]
vector<set<int>> BB;
for(auto z: B) {
BB.emplace_back(set<int>(z.begin(),z.end()));
}
// M = 3
// [1 0 1]
// [1 1 1]
// [1 1 0]
// [0 0 1] N-M = 3
// [1 1 0]
// [0 1 1]
vector<vector<int>> dp1(N, vector<int>(M,0));
vector<pair<int,int>> segs;
for(int y = N-1; y >= 0; --y){
for(int x = 0; x < M; ++x){
if(BB[x].count(C[y])) {
if(y == N-1) dp1[y][x] = 1;
else dp1[y][x] = dp1[y+1][(x+1)%M]+1;
}
if(y <= N-M && dp1[y][x] >= M) segs.emplace_back(y,y+M-1);
}
}
sort(segs.begin(),segs.end());
vector<int> dp(N,INF);
for(auto z: segs){
int l = z.first, r = z.second;
if(l == 0) dp[r] = 1;
else {
for(int d = l-1; d < r; ++d){
dp[r] = min(dp[d]+1,dp[r]);
}
}
}
if(dp[N-1] == INF) return -1;
else return dp[N-1];
};
