#include "paint.h"
#include <vector>
#include <set>
#include <cstdio>
using namespace std;
set<int> coltoconst[100005];
int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < a[i]; j++) coltoconst[b[i][j]].insert(i);
}
int init = 0;
int ans = 0;
bool okay = true;
set<int> cur;
// printf("here\n");
cur = coltoconst[c[0]];
for (int i = 1; i < n; i++) {
// printf("%d here\n", i);
set<int> tempcur;
for (auto u: cur) {
// printf("%d here\n", i);
if (coltoconst[c[i]].find((u+i)%m) != coltoconst[c[i]].end()) tempcur.insert(u);
}
cur = tempcur;
// printf("%d: ", i);
// for (auto u: cur) printf ("%d ", u);
// printf ("\n");
// printf("%d here\n", i);
if (cur.empty() || i == n-1) {
if (i - init < m && i != n-1) okay = false;
if (i - init < m - 1 && i == n-1) okay = false;
ans += (i-init-1)/m + 1;
init = i;
for (auto u: coltoconst[c[i]]) {
if (u - i >= 0) cur.insert((u - i)%m);
else cur.insert((u-i)%m + m);
}
}
// printf("%d: ", i);
// for (auto u: cur) printf ("%d ", u);
// printf ("\n");
// printf("%d here\n", i);
}
if (!okay) return -1;
return ans;
}
