#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
typedef bitset<50000> mask;
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B)
{
vector<mask> contractors(K);
for (int i = 0; i < M; i++)
for (int c : B[i])
contractors[c][i] = 1;
int ans = 0;
for (int i = 0; i < N; i++)
{
ans++;
int R = -1;
mask yay = contractors[C[i]], last;
for (int l = 0; l < M; l++)
{
last = yay;
// we can only use contractor x on wall i if we can use contractor x+l on wall i+l.
// thus we want the x'th bit of mask[i] to be set, and the x+l'th bit of mask[i+l] to be set.
yay &= (contractors[C[i+l]] >> l) | (contractors[C[i+l]] << (M-l));
if (yay.count() == 0)
{
R = i + l - 1;
break;
}
}
if (R == -1)
{
R = i + M - 1;
i = R;
continue;
}
int L = N;
yay = last;
int remaining = M - (R - i + 1);
if (i < remaining)
return -1;
for (int l = -1; -l <= -remaining; l--)
{
last = yay;
yay &= (contractors[C[i+l]] >> l) | (contractors[C[i+l]] << (M-l));
if (yay.count() == 0)
{
L = i + l + 1;
break;
}
}
if (L == N)
{
i = R;
continue;
}
return -1;
}
return ans;
}
