CF959B.Mahmoud and Ehab and the message

普及-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Mahmoud wants to send a message to his friend Ehab. Their language consists of n words numbered from 1 to n. Some words have the same meaning so there are k groups of words such that all the words in some group have the same meaning.

Mahmoud knows that the i-th word can be sent with cost a__i. For each word in his message, Mahmoud can either replace it with another word of the same meaning or leave it as it is. Can you help Mahmoud determine the minimum cost of sending the message?

The cost of sending the message is the sum of the costs of sending every word in it.

马哈茂德想给他的朋友埃哈卜发送一条消息。他们的语言由 nn 个单词组成,编号从 11 到 nn。其中一些单词含义相同,因此这些单词被划分为 kk 个组,同一组内的所有单词含义完全相同。

马哈茂德知道第 ii 个单词的发送成本为 aia_i。对于消息中的每个单词,他可以选择用另一个同义词(即同一组中的其他单词)来替换它,也可以保持原词不变。你能帮马哈茂德计算出发送该消息的最小总成本吗?

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

输入格式

The first line of input contains integers n, k and m (1 ≤ k ≤ n ≤ 105, 1 ≤ m ≤ 105) — the number of words in their language, the number of groups of words, and the number of words in Mahmoud's message respectively.

The second line contains n strings consisting of lowercase English letters of length not exceeding 20 which represent the words. It's guaranteed that the words are distinct.

The third line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109) where a__i is the cost of sending the i-th word.

The next k lines describe the groups of words of same meaning. The next k lines each start with an integer x (1 ≤ x ≤ n) which means that there are x words in this group, followed by x integers which represent the indices of words in this group. It's guaranteed that each word appears in exactly one group.

The next line contains m space-separated words which represent Mahmoud's message. Each of these words appears in the list of language's words.

输入的第一行包含三个整数 nn、kk 和 mm(1 ≤ k ≤ n ≤ 1051 ≤ k ≤ n ≤ 10^5,1 ≤ m ≤ 1051 ≤ m ≤ 10^5)—— 分别表示该语言中单词的总数、同义词组的数量,以及 Mahmoud 消息中单词的数量。

第二行包含 nn 个字符串,均由小写英文字母组成,每个字符串长度不超过 20,代表该语言中的所有单词。保证这些单词互不相同。

第三行包含 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n(1 ≤ ai ≤ 1091 ≤ a_i ≤ 10^9),其中 aia_i 表示发送第 ii 个单词的代价。

接下来的 kk 行描述了各组同义词。每行以一个整数 xx(1 ≤ x ≤ n1 ≤ x ≤ n)开头,表示该组包含 xx 个单词,随后是 xx 个整数,表示该组中各单词在单词列表中的下标(从 1 开始计数)。保证每个单词恰好出现在一个组中。

下一行包含 mm 个用空格分隔的单词,代表 Mahmoud 的消息。消息中的每个单词均出现在上述语言单词列表中。

输出格式

The only line should contain the minimum cost to send the message after replacing some words (maybe none) with some words of the same meaning.

唯一的一行应包含在将某些单词(可能不替换任何单词)替换成具有相同含义的其他单词之后,发送该消息的最小花费。

输入输出样例

  • 输入#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

说明/提示

In the first sample, Mahmoud should replace the word "second" with the word "loser" because it has less cost so the cost will be 100+1+5+1=107.

In the second sample, Mahmoud shouldn't do any replacement so the cost will be 100+1+5+10=116.

在第一个样例中,马哈茂德应将单词“second”替换为单词“loser”,因为其代价更小,因此总代价为 100+1+5+1=107100+1+5+1=107。

在第二个样例中,马哈茂德不应进行任何替换,因此总代价为 100+1+5+10=116100+1+5+10=116。

输入解题思路,AI测评打分。不知道怎么写?

首页