#include <bits/stdc++.h>
#include "paint.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
// #define int long long int
// const int N = 1000 + 10;
// const int md = 1e9 + 7;
// const int INF = 5e6;
int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b) {
vector<vector<bool>> ok(n + 1, vector<bool> (m + 1));
for (int i = 0; i < m; i++) {
vector<bool> qw(k + 1);
for (int j = 0; j < a[i]; j++)
qw[b[i][j]] = 1;
for (int j = 0; j < n; j++) {
if (qw[c[j]] == 1)
ok[j][i] = 1;
}
}
vector<vector<int>> dp(n + 2, vector<int> (m + 2));
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < m; j++) {
if (ok[i][j]) {
dp[i][j] = dp[i + 1][j + 1] + 1;
}
}
}
vector<int> v;
for (int i = 0; i <= (n - m); i++) {
for (int j = 0; j < m; j++) {
if (j == 0) {
if (dp[i][j] == m)
v.push_back(i);
} else {
if (dp[i][j] == (m - j) && dp[i + (m - j)][0] >= j)
v.push_back(i);
}
}
}
int ans = 0;
int el = n - 1;
while (el != -1) {
int l = lower_bound(v.begin(), v.end(), (el - m + 1)) - v.begin();
if (l == (int) v.size() || v[l] > el) {
ans = -1;
break;
} else {
ans++;
el = v[l] - 1;
}
}
return ans;
}
// int32_t main(int32_t argc, char *argv[]) {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int T = 1;
// // cin >> T;
// while (T--) {
// vector<int> c = {3, 3, 1, 3, 4, 4, 2, 2};
// vector<vector<int>> b = {{0, 1, 2}, {2, 3}, {3, 4}};
// vector<int> a = {3, 2, 2};
// cout << minimumInstructions(8, 3, 5, c, a, b) << '\n';
// }
// return 0;
// }
