时间限制： 1.0 秒

空间限制： 512 MB

题目描述

在一个热门的元宇宙游戏中，小 b 购置了一座豪华的虚拟房产，现在他需要为这个房子添置若干家具。为了制作这些家具，他需要 $N~(1\le N \le 100)$ 种特定的材料。

游戏中总共有 $M~(1\le M\le 10^4)$ 种材料，它们的获取分为两类：

1. 直接获取的材料： 这些材料只需要付出相应的成本就可以获得。
2. 通过合成获取的材料： 这些材料无法获取，必须通过合成的方式获得。

除了以上两种方式，小 b 还可以通过以下两种途径获取材料：

1. 与其他玩家交换： 小 b 了解到小区内有 $P~(0\le P\le 5)$ 个邻居也在准备家具，并且他们有一些多出来的材料。对于邻居 $j$，他多出来了材料 $r_j$，并且希望小 b 可以用他所需的材料 $s_j$ 来换取 $r_j$。小 b 只能与每个邻居交换至多一次。
2. 购买官方售卖的材料礼包： 官方售卖的材料礼包共有 $Q~(0\le Q\le 5)$ 种，这些礼包包含多种材料，购买礼包中的所有材料。每个礼包只能购买至多一次。

小 b 想要知道，如何以最小的成本来获得所需的 $N$ 种材料。

输入格式

从标准输入读入数据。

第一行包含四个整数 $N,M,P,Q$，其中 $N~(1\le N\le 100)$ 表示小 b 所需的材料种数，$M~(1\le M\le 10^4)$ 表示素材的总种类数，$P~(0\le P\le 5)$ 表示邻居的个数，$Q~(0\le Q\le 5)$ 表示礼包的个数。素材编号为 $1,2,\cdots,M$。

接下来一行，描述了小 b 所需的材料列表，它包含 $N$ 个正整数素材编号。

接下来 $M$ 行，描述了每种素材的获取方式。

• 如果这种素材是直接获取的，则输入为 $0,c_i~(1\le c_i\le 100)$，其中 $c_i$ 是这种素材的成本。
• 如果这种素材是需要合成的，则第一个数为一个正整数 $a_i~(a_i>0)$，表示合成所需的素材个数。然后紧跟这 $a_i$ 个正整数，表示合成所需素材的编号列表。保证每种素材至多只会作为一种素材的合成材料，并且素材之间的合成关系不会成环。

之后的 $P$ 行，每行有两个整数 $s_j,r_j~(1\le s_j,r_j\le M)$，表示可以用素材 $s_j$ 交换素材 $r_j$。注意交换是单向的，不可以使用素材 $r_j$ 来交换素材 $s_j$。

最后的 $Q$ 行，每行描述了一个礼包，第一个数为一个正整数 $u_k~(u_k\le 100)$，表示礼包所包含的素材个数，然后是一个正整数 $w_k~(1\le w_k\le 10^4)$，表示礼包的成本。之后跟随 $u_k$ 个整数，表示礼包包含的材料编号列表。

输出格式

输出到标准输出。

输出一个整数，表示小 b 获取所需材料的最小成本。

1 7 0 0
1
3 2 3 4
3 5 6 7
0 2
0 3
0 5
0 6
0 3

19

样例 1 解释

最优方案为：

• 获取素材 $5,6,7$ 并合成为素材 $2$，花费 $5+6+3=14$；
• 获取素材 $3,4$，花费 $2+3=5$；
• 使用素材 $2,3,4$ 来合成素材 $1$。

总成本为 $14+5=19$。

3 6 2 2
1 2 3
2 2 3
1 4
0 2
0 6
0 3
0 8
6 1
3 4
2 9 4 6
2 6 5 6

10

样例 2 解释

最优方案为：

• 购买素材礼包 $2$，获取素材 $5,6$，花费 $6$，然后通过素材 $6$ 交换得到素材 $1$；
• 获取素材 $3$，交换得到素材 $4$，然后合成素材 $2$，花费 $2$；
• 获取素材 $3$，花费 $2$。

总成本为 $6+2+2=10$。

子任务

对于所有的数据，满足 $1\le N\le 100,~1\le s_j,r_j\le M\le 10^4,~0\le P,Q\le 5,~1\le c_k,u_k\le 100,~1\le w_k\le 10^4$。