题目描述

注意：在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++ 11
• C++ 11 (Clang)
• C++ 11 (NOI)
• C++ 17
• C++ 17 (Clang)

距离上一次 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}$ 种颜色，$\ldots$，或第 $B_{j, A_j -1}$ 种颜色。

Pak Dengklek 可以给承包商公司提出一些要求。在单个要求中，Pak Dengklek 将给出两个参数 $x$ 和 $y$，其中 $0 \le x \lt M, 0 \le y \le N - M$。承包商公司将会指派第 $((x + l) \bmod M)$ 个承包商粉刷第 $(y + l)$ 段墙壁，其中 $0 \le l \lt M$。如果存在一个 $l$ 使得第 $((x + l) \bmod M)$ 个承包商不喜欢第 $C_{y+l}$ 种颜色，那么该要求将无效。

Pak Dengklek 需要为每个要求付费，因此他想知道为了使墙壁中每个段都能用自己预期的颜色粉刷，他至少要提出多少个要求，或是确认他的预期无法达到。每一段墙壁可以被粉刷多次，但必须保证每次粉刷的颜色都是 Pak Dengklek 所预期的。

实现细节

你必须引用 paint.h 头文件。

你必须实现 minimumInstructions 函数：

int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> 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 的返回值。

样例 1

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

3

$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 可以提出下列的要求。

$x = 1, y = 0.$ 这是一个有效的要求，第一个承包商可以粉刷第零段墙壁，第二个承包商可以粉刷第一段墙壁，第零个承包商可以粉刷第二段墙壁。 $x = 0, y = 2.$ 这是一个有效的要求，第零个承包商可以粉刷第二段墙壁，第一个承包商可以粉刷第三段墙壁，第二个承包商可以粉刷第四段墙壁。 $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$。

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

-1

$N = 5, M = 4, K = 4, C = [1, 0, 1, 2, 2]$。由于第三个承包商只喜欢第 $3$ 种颜色但没有任何一段墙壁能被该颜色粉刷，Pak Dengklek 无法给出任何有效指令。因此 minimumInstructions(5, 4, 4, [1, 0, 1, 2, 2], [2, 1, 1, 1], [[0, 1], [1], [2], [3]]) 应该返回 $-1$。

数据范围与提示

对于 $0 \le k \lt K$, 令 $f(k)$ 表示喜欢第 $k$ 种颜色的承包商数量。

• $1 \le N \le 100\,000$
• $1 \le M \le \min(N, 50\,000)$
• $1 \le K \le 100\,000$
• $0 \le C_i \lt K$
• $1 \le A_j \le K$
• $0 \le B_{j,0} \lt B_{j,1} \lt \ldots \lt B_{j,A_j-1} \lt K$
• $\sum f(k)^2 \le 400\,000$