2021 年标志着 Adobe Flash 的终结，这是一款用于动画、应用程序、游戏等的流媒体软件。伴随着它的逝去，Flash 游戏的时代（尤其是 2005 年至 2012 年）也开始逐渐消逝在历史的长河中。不过在这方面也有一些好消息，人们已经在努力寻找保存 Flash 内容的方法。其中主要的努力包括 Ruffle（一个用 Rust 编写的开源 Flash 播放器）和 Flashpoint（一个收录了超过 78,000 个 Flash 应用程序的存档）。

为了纪念 Flash 游戏的黄金时代，我们推出了著名 Flash 游戏《制造球》（Factory Balls）的一个简化版本。你的任务是将一个球涂成给定的图案。球的表面可以分为 $N$ 个不同的区域，编号为 $1$ 到 $N$。你有 $K$ 罐装满油漆的油漆罐，其中第 $i$ 个油漆罐的颜色为 $i$。你还得到了 $M$ 件装备。每件装备由一组区域指定，它恰好覆盖球上对应的区域子集。

最开始，所有区域的颜色均为 1，且所有装备都未装备。你可以执行以下任意操作任意次数：

1. 将球浸入第 $i$ 个油漆罐中。此时，球上未被任何已装备的装备覆盖的所有区域都将被染成颜色 $i$。
2. 选择一件当前未装备的装备，并装备它。你可以同时装备多件装备。
3. 选择一件当前已装备的装备，并卸下它。

最终，球的每个区域都应该具有指定的颜色，并且所有装备都必须处于未装备状态。求涂好这个球所需的最少操作次数，如果无法实现，则输出 -1。

输入格式

第一行包含三个整数：$N$，$K$ 和 $M$。

下一行包含 $N$ 个整数。第 $i$ 个整数 $c_i$ 表示第 $i$ 个区域的目标颜色。

接下来的 $M$ 行中，每行描述一件装备。每行的第一个数字 $r_j$ 表示该装备覆盖的区域数量，随后是 $r_j$ 个互不相同的正整数，表示该装备覆盖的区域编号。

• $1 \leq N, K \leq 10$
• $0 \leq M \leq 10$
• $1 \leq c_i \leq K$
• $1 \leq r_j \leq N$，且对于每件装备，其覆盖的所有区域编号互不相同。

输出格式

如果无法将球的每个区域涂成给定的颜色，输出 -1。否则，输出所需的最少操作次数。

样例

输入样例 1

3 5 3
1 3 5
1 1
1 2
1 3

输出样例 1

6

输入样例 2

4 3 2
3 3 2 1
2 1 2
2 2 3

输出样例 2

7

输入样例 3

4 2 2
1 2 2 1
2 1 2
2 3 4

输出样例 3

-1

输入样例 4

2 10 0
1 1

输出样例 4

0

说明

在第二个样例中，最快的方法如下：

• 将球浸入第三个油漆罐中。
• 装备第一件装备。
• 将球浸入第二个油漆罐中。
• 装备第二件装备。
• 将球浸入第一个油漆罐中。
• 卸下两件装备。