装修

题目描述

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

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

1. 直接获取的材料：这些材料只需要付出相应的成本就可以获得。

2. 通过合成获取的材料：这些材料无法直接获取，必须通过合成的方式获得。

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

1. 与其他玩家交换：小b了解到小区内有 $P(0 \leq P \leq 5)$ 个邻居也在准备家具，并且他们有一些多出来的材料。对于邻居 $j$，他多出来了材料 $r_j$，并且希望小b可以用他所需的材料 $s_j$ 来换取 $r_j$ 。小 $b$ 只能与每个邻居交换至多一次。

2. 购买官方售卖的材料礼包：官方售卖的材料礼包共有 $Q(0≤Q≤5)$ 种，这些礼包包含多种材料，购买礼包将会获得礼包中的所有材料。每个礼包只能购买至多一次。

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

输入格式

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

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

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

• 如果这种素材是直接获取的，则输入为0; $ci (1 \leq c_i \leq 100)$，其中 $c_i$ 是这种素材的成本。

• 如果这种素材是需要合成的，则第一个数为一个正整数 $a_i (ai > 0)$ ，表示合成所需的素材个数。然后紧跟这 $a_i$ 个正整数表示合成所需素材的编号列表。保证每种素材至多只会作为一种素材的合成材料，并且素材之间的合成关系不会成环。

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

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

19

提示

【样例 $1$ 解释】

最优方案为：

•获取素材 $5;6;7$ 并合成为素材 $2$ ，花费 $5+6+3=14$ ；

•获取素材 $3;4$ ，花费 $2+3=5$ ；

•使用素材 $2;3;4$ 来合成素材 $1$ 。

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

【样例 $2$ 解释】

最优方案为：

•购买素材礼包 $2$ ，获取素材 $5;6$ ，花费 $6$ ，然后通过素材 $6$ 交换得到素材 $1$ ；

•获取素材 $3$ ，交换得到素材 $4$ ，然后合成素材 $2$ ，花费 $2$ ；

•获取素材 $3$ ，花费 $2$ 。

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

对于所有的数据，满足 $1≤N≤100，1≤s_j;r_j ≤M≤10^4，0≤P;Q≤5， 1≤c_i;u_k≤100，1≤w_k≤10^4$