#include "paint.h"
#include <vector>
#include <unordered_set>
// #include <iostream>
using namespace std;
vector<int> dp(1000000,1e9);
vector<vector<int>> colors(1000000,vector<int>());
int minimumInstructions(int N, int M, int K, std::vector<int> C,std::vector<int> A, std::vector<std::vector<int>> B) {
vector<unordered_set<int>> contrcatorColor(M,unordered_set<int>());
for(int i=0;i<M;i++){
for(int j=0;j<A[i];j++){
colors[B[i][j]].push_back(i);
contrcatorColor[i].insert(B[i][j]);
}
}
bool possible = true;
for(int i=0;i<=(N-M);i++){
// cout << "start pos is " << i << endl;
bool coloured = false;
for(int j=0;j<(int)colors[C[i]].size();j++){
int contractorStart = colors[C[i]][j];
possible = true;
// cout << "contractor start " << contractorStart << endl;
for(int k=0;k<M;k++){
// cout << (contractorStart+k)%M << " contractor " << C[i+k] << " color " << contrcatorColor[(contractorStart+k)%M].count(C[i+k]) << endl;
if(contrcatorColor[(contractorStart+k)%M].count(C[i+k]) == 0){
possible = false;
break;
}
}
if(possible){
// cout << "possible to paint " << i << " start from " << contractorStart << endl;
coloured = true;
break;
}
}
if(coloured){
// cout << "i-" << i;
if(i>0){
// cout << " dp[i-1]" << dp[i-1];
dp[(M-1+i)] = dp[i-1]+1;
}else{
// cout << "start ";
dp[(M-1+i)] = 1;
}
dp[(M-1+i)] = min(dp[(M-1+i)],dp[i]+1);
dp[(M-1+i)] = min(dp[(M-1+i)],dp[i+1]+1);
// cout << " pos-" << (M-1+i) << " dp[M-1]-" << dp[(M-1+i)] << endl;
}
// cout << endl;
}
// for(int i=0;i<N;i++){
// cout << dp[i] << " ";
// }cout << endl;
if(dp[N-1] >= 1e9){
return -1;
}
return dp[N-1];
}
