由于某些原因本题仅支持 C++ 各版本语言的提交。

距离上一次 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]$ 种颜色，$\cdots$，或第 $B[j][A[j]−1]$ 种颜色。

Pak Dengklek 可以给承包商公司提出一些要求。在单个要求中，Pak Dengklek 将 给出两个参数 $x$ 和 $y$, 其中 $0 \le x < M$ , $0 \le y \le N − M$。承包商公司将会指派第 $((x + l)\ \bmod M)$ 个承包商粉刷第 $(y + l)$ 段墙壁，其中 $0 \le l < 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]\ \cdots \ C[N-1]$

$A[0]\ B[0][0]\ B[0][1]\ \cdots \ B[0][A[0]-1]$

$A[1]\ B[1][0]\ B[1][1]\ \cdots \ B[1][A[1]-1]$

$\cdots$

$\cdots$

$A[M-1]\ B[M-1][0]\ B[M-1][1]\ \cdots \ 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

限制与约定

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

对于所有测试数据：

• $1 \le N \le 100000.$
• $1 \le M \le \min(N,50000)$
• $1 \le K \le 100000.$
• $0 \le C[i] < K$.
• $1 \le A[j] \le K$
• $0 \le B[j][0] < B[j][1] < ... < B[j][A[j]−1] < K$.
• $\sum f(k)^2 \le 400000$.

实际测试中，前 8 个 subtask 为数据包，后 5 个 subtask 为 5 个子任务。

时间限制：$2 \texttt{s}$

空间限制：$512 \texttt{MB}$

　下载

样例及测评库下载