题目背景

由于官方数据包过大，本题仅评测部分数据。

本题仅支持 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$ 分）】

• 无附加限制。