#10143. CCSP2023A. 装修

时间限制： 1.0 秒

空间限制： 512 MB

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

游戏中总共有 种材料，它们的获取分为两类：

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

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

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

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

从标准输入读入数据。

第一行包含四个整数 ，其中 表示小 b 所需的材料种数， 表示素材的总种类数， 表示邻居的个数， 表示礼包的个数。素材编号为 。

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

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

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

之后的 行，每行有两个整数 ，表示可以用素材 交换素材 。注意交换是单向的，不可以使用素材 来交换素材 。

最后的 行，每行描述了一个礼包，第一个数为一个正整数 ，表示礼包所包含的素材个数，然后是一个正整数 ，表示礼包的成本。之后跟随 个整数，表示礼包包含的材料编号列表。

输出到标准输出。

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

样例 1 解释

最优方案为：

• 获取素材 并合成为素材 ，花费 ；
• 获取素材 ，花费 ；
• 使用素材 来合成素材 。

总成本为 。

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 解释

最优方案为：

• 购买素材礼包 ，获取素材 ，花费 ，然后通过素材 交换得到素材 ；
• 获取素材 ，交换得到素材 ，然后合成素材 ，花费 ；
• 获取素材 ，花费 。

总成本为 。

子任务

对于所有的数据，满足 。