[APIO2020] 粉刷墙壁

由于官方数据包过大，本题仅评测部分数据。 本题仅支持 C++ 系列语言，提交时**不需要**包含 `paint.h` 头文件。 如果交互库存在其他问题，请私信 mrsrz。

距离上一次 Pak Dengklek 在他的家中粉刷墙壁已经过了一段时间，所以他想重新粉刷一次。他家的墙壁由 $N$ 段组成，它们从 $0$ 到 $N - 1$ 编号。本题中我们假设存在 $K$ 种不同的颜色，颜色用从 $0$ 到 $K - 1$ 的整数表示（例如，红色用 $0$ 表示, 蓝色用 $1$ 表示，以此类推）。Pak Dengklek 希望用第 $C[i]$ 种颜色来粉刷第 $i$ 段的墙壁。 为了粉刷墙壁，Pak Dengklek 雇用了一家有 $M$ 个承包商的承包商公司，承包商从 $0$ 到 $M - 1$ 编号。对 Pak Dengklek 来说不幸的是，承包商只愿意粉刷他们自己喜欢的 颜色。具体来说，第 $j$ 个承包商喜欢 $A[j]$ 种颜色，并且只想用下列颜色来粉刷墙壁：第 $B[j][0]$ 种颜色，第 $B[j][1]$ 种颜色，$\dots$，或第 $B[j][A[j] − 1]$ 种颜色。 Pak Dengklek 可以给承包商公司提出一些要求。在单个要求中，Pak Dengklek 将给出两个参数 $x$ 和 $y$， 其中 $0 \leq x < M$，$0 \leq y \leq N - M$。承包商公司将会指派第 $((x + l) \mod M)$ 个承包商粉刷第 $(y + l)$ 段墙壁，其中 $0 \leq l < M$。如果存在一个 $l$ 使 得第 $((x + l) \mod M)$ 个承包商不喜欢第 $C[y + l]$ 种颜色，那么该要求将无效。 Pak Dengklek 需要为每个要求付费，因此他想知道为了使墙壁中每个段都能用自己预期的颜色粉刷，他至少要提出多少个要求，或是确认他的预期无法达到。每一段墙壁可以被粉刷多次，但必须保证每次粉刷的颜色都是 Pak Dengklek 所预期的。 你必须实现 `minimumInstructions` 函数： - `minimumInstructions(N, M, K, C, A, B)` - 该函数将被评测库恰好调用一次。 - $N$：一个整数表示墙壁的段数。 - $M$：一个整数表示承包商的数量。 - $K$：一个整数表示颜色的种数。 - $C$：一个长度为 $N$ 的整数序列，表示每段墙壁预期的颜色。 - $A$：一个长度为 $M$ 的整数序列，表示承包商喜欢的颜色数。 - $B$：一个长度为 $M$ 的每个元素为序列的序列，表示承包商喜欢的具体颜色。 - 该函数必须返回一个整数，表示 Pak Dengklek 为了让墙壁按预期粉刷所需要提出的最小要求数；若预期无法达到则返回 $-1$。

样例评测库将读入以下格式的数据： ``` N M K C[0] C[1] ... C[N-1] A[0] B[0][0] B[0][1] ... B[0][A[0]-1] A[1] B[1][0] B[1][1] ... B[1][A[1]-1] . . . A[M-1] B[M-1][0] B[M-1][1] ... B[M-1][A[M-1]-1] ```

样例评测库将输出函数 `minimumInstructions` 的返回值

8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4

3

5 4 4
1 0 1 2 2
2 0 1
1 1
1 2
1 3

-1

在第一个样例中， $N = 8$，$M = 3$，$K = 5$，$C = [3, 3, 1, 3, 4, 4, 2, 2]$，$A = [3, 2, 2]$，$B = [[0, 1, 2], [2, 3], [3, 4]]$。Pak Dengklek 可以提出下列的要求。 1. $x = 1$，$y = 0$。这是一个有效的要求，第一个承包商可以粉刷第零段墙壁，第二个承包商可以粉刷第一段墙壁，第零个承包商可以粉刷第二段墙壁。 2. $x = 0$，$y = 2$。 这是一个有效的要求，第零个承包商可以粉刷第二段墙壁，第一个承包商可以粉刷第三段墙壁，第二个承包商可以粉刷第四段墙壁。 3. $x = 2$，$y = 5$。 这是一个有效的要求，第二个承包商可以粉刷第五段墙壁，第零个承包商可以粉刷第六段墙壁，第一个承包商可以粉刷第七段墙壁。 容易看出 Pak Dengklek 不能用少于 $3$ 个的要求来达到预期，因此 `minimumInstructions(8, 3, 5, [3, 3, 1, 3, 4, 4, 2, 2], [3, 2, 2], [[0, 1, 2], [2, 3], [3, 4]])` 应该返回 $3$。 在第二个样例中，$N = 5$，$M = 4$，$K = 4$，$C = [1, 0, 1, 2, 2]$，$A = [2, 1, 1, 1]$，$B = [[0, 1], [1], [2], [3]]$。由于第三个承包商只喜欢第 $3$ 种颜色但没有任何一段墙壁能被该颜色粉刷，Pak Dengklek 无法给出任何有效指令。因此`minimumInstructions(5, 4, 4,[1, 0, 1, 2, 2], [2, 1, 1, 1], [[0, 1], [1], [2], [3]])` 应该返回 $-1$。 对于 $0 \leq k < K$, 令 $f(k)$ 表示喜欢第 $k$ 种颜色的承包商数量。 【条件限制】 - $1 \leq N \leq 100 000$。 - $1 \leq M \leq \min(N, 50 000)$。 - $1 \leq K \leq 100 000$。 - $0 \leq C[i] < K$。 - $1 \leq A[j] \leq K$。 - $0 \leq B[j][0] < B[j][1] < \dots < B[j][A[j] − 1] < K$。 - $\sum f(k)^2 \leq 400 000$。 【子任务 $1$（$12$ 分）】 - $f(k) \leq 1$。 【子任务 $2$（$15$ 分）】 - $N \leq 500$。 - $M \leq \min(N, 200)$。 - $\sum f(k)^2 \leq 1 000$。 【子任务 $3$（$13$ 分）】 - $N \leq 500$。 - $M \leq \min(N, 200)$。 【子任务 $4$（$23$ 分）】 - $N \leq 20 000$。 - $M \leq \min(N, 2 000)$。 【子任务 $5$（$37$ 分）】 - 无附加限制。