Description

盼盼在玩一款游戏，名叫“末日方舟”。他负责分配他已有的干员去通关关卡。每一个干员都有各自的职业和能力。盼盼需要分配自己的干员到队伍中，为了保证队伍中干员的多样化，盼盼规定一个队伍里必须每种职业的干员各有一个，否则不能构成队伍。队伍的能力值为队伍中所有干员的能力值之和。在“末日方舟”这个游戏中，一些干员也有自己的国度（特别的，一些干员不只属于一个国度）。当一个国度上所有的干员都被安排到队伍中时，该队伍就会有额外的能力值加成。盼盼想知道如何分配自己拥有的干员进入队伍，使队伍所具有的能力值最大。

Input Format

第一行给出一个整数$N， M， C， D$，（$1 \le C \le D \le N \le 10^5, 1 \le M \le min(100, N) $）表示盼盼具有的干员总数，国度总数，职业总数，和所需要上场的干员数。

第二行给出$N$个整数，第$i$个整数$a_i$($0 \le a_i \le 10^5$)表示第$i$个干员的能力值。（数据保证每种职业至少有一个干员）

第三行给出$N$个整数，第$i$个整数$b_i$($1 \le b_i \le C$)表示第$i$个干员是第$b_i$种职业。

接下来$M$行，第$i$行先给出两个整数$X, K$($0 \le X \le 10^5,\frac{D+1}{2} \le K \le D$),$X$表示第$i$个国度的所有干员都上场时队伍所额外获的能力值。接下来会给出$K$个整数$c_i$($1\le c_i \le N$)，表示该国度所包含的干员编号。

Output Format

输入一行一个整数，表示盼盼为了通关所安排的队伍的能力值最大是多少。

7 3 4 5
2 2 3 4 5 6 9
1 1 4 3 3 2 3
3 3 4 7 1
4 4 1 2 3 4
5 4 5 4 3 2

27

7 3 4 5
2 2 3 4 10 6 9
1 1 4 3 3 2 3
3 3 4 7 1
4 4 1 2 3 4
5 4 5 4 3 2

30

Source

1816 Online Judge 10.100.0.232