← 返回题目列表

Codeforces · 959/B

B. Mahmoud 和 Ehab 以及消息

中文机器翻译题面 查看原题

Mahmoud 想向他的朋友 Ehab 发送消息。他们的语言由编号为 1 到 n 的 n 个单词组成。有些单词具有相同的含义,因此有 k 组单词,使得某个组中的所有单词都具有相同的含义。

Mahmoud 知道第 i 个单词可以用成本 ai 发送。对于消息中的每个单词,马哈茂德可以用另一个具有相同含义的单词替换它,也可以保持原样。你能帮助马哈茂德确定发送消息的最低成本吗?

发送消息的成本是发送其中每个单词的成本之和。

输入

输入的第一行包含整数 n、k 和 m (1 ≤ k ≤ n ≤ 105, 1 ≤ m ≤ 105) - 分别是其语言中的单词数、单词组数以及 Mahmoud 消息中的单词数。

第二行包含n个长度不超过20的小写英文字母组成的字符串,代表单词。保证单词清晰。

第三行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109),其中 ai 是发送第 i 个字的成本。

接下来的 k 行描述了具有相同含义的单词组。接下来的 k 行每行以整数 x (1 ≤ x ≤ n) 开头,这意味着该组中有 x 个单词,后面跟着 x 个整数,表示该组中单词的索引。保证每个单词恰好出现在一组中。

下一行包含 m 个空格分隔的单词,代表 Mahmoud 的消息。这些单词中的每一个都出现在语言单词列表中。

输出

唯一的一行应该包含用一些相同含义的单词替换一些单词(可能没有)后发送消息的最小成本。

示例

输入 #1

5 4 4
i loser am the second
100 1 1 5 10
1 1
1 3
2 2 5
1 4
i am the second

输出 #1

107

输入 #2

5 4 4
i loser am the second
100 20 1 5 10
1 1
1 3
2 2 5
1 4
i am the second

输出 #2

116

注意

在第一个示例中,Mahmoud 应将“第二”一词替换为“失败者”一词,因为它的成本较小,因此成本将为 100+1+5+1=107。

在第二个示例中,Mahmoud 不应进行任何替换,因此成本将为 100+1+5+10=116。