#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A, vector<vector<int>> B)
{
vector<vector<int>> likes(K);
for(int j = 0;j < B.size();++j)
{
for(int k = 0;k < B[j].size();++k)
{
likes[B[j][k]].push_back(j);
}
}
vector<int> p(M,-1);
vector<vector<int>> dp(N);
vector<int> mdp(N,0);
for(int i = N-1;i >= 0;--i)
{
dp[i].resize(likes[C[i]].size());
for(int j = 0;j < likes[C[i]].size();++j)
{
int cp = likes[C[i]][j];
dp[i][j] = (p[(cp+1)%M] == -1 ? 1 : p[(cp+1)%M]+1);
mdp[i] = max(mdp[i],dp[i][j]);
}
if(i != N-1)
{
for(int j = 0;j < likes[C[i+1]].size();++j)
{
p[likes[C[i+1]][j]] = -1;
}
}
for(int j = 0;j < likes[C[i]].size();++j)
{
p[likes[C[i]][j]] = dp[i][j];
}
}
vector<int> ans(N+1,N+2);
ans[N] = 0;
multiset<int> bm;
bm.insert(0);
for(int i = N-1;i >= 0;--i)
{
if(mdp[i] >= M)
{
ans[i] = *bm.begin() + 1;
}
if(i + M <= N)
{
bm.erase(bm.find(ans[i+M]));
}
bm.insert(ans[i]);
}
return (ans[0] == N+2 ? -1 : ans[0]);
}
