Олимпиадный тренинг

Задача . B. Махмуд, Эхаб и сообщение


Задача

Темы: реализация жадные алгоритмы *1200 снм

Махмуд хочет послать сообщение своему другу Эхабу. Их язык состоит из n слов, пронумерованных с 1 по n. У некоторых слов совпадают значения, поэтому существует k групп слов таких, что у всех слов в одной группе значение одинаковое.

Махмуд знает, что стоимость посылки i-го слова равна ai. Каждое слово в сообщении Махмуд может оставить неизменным или заменить его другим словом с тем же значением. Можете ли вы помочь Махмуду определить минимальную стоимость посылки сообщения?

Стоимость посылки сообщения равна сумме стоимостей отправки всех слов в сообщении.

Входные данные

В первой строке ввода содержатся три целых числа n, k и m (1 ≤ k ≤ n ≤ 105, 1 ≤ m ≤ 105) — число слов в языке, число групп слов с одинаковым значением и число слов в сообщении Махмуда соответственно.

Во второй строке содержится n строк, разделённых пробелами, состоящих из строчных (маленьких) английских букв, длиной не более 20 символов — слова языка Махмуда. Гарантируется, что слова различны.

В третьей строке содержится n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109), где ai — стоимость посылки i-го слова.

Далее следуют k строк, описывающих группы слов, одинаковых по значению. Каждая из следующих k строк начинается с целого числа x (1 ≤ x ≤ n), что означает, что в данной группе синонимов x слов, после чего следует x целых чисел — номера слов, имеющих одинаковое значение в языке Махмуда. Гарантируется, что каждое слово встречается ровно в одной группе.

Следующая строка содержит m слов, разделённых пробелами — сообщение, которое хочет послать Махмуд. Каждое из этих слов встречается в списке слов языка.

Выходные данные

Единственная строка вывода должна содержать минимальную стоимость посылки сообщения после замены нескольких (возможно, ни одного) слова другими словами с таким же значением.

Примечание

В первом примере Махмуд должен заменить слово «second» на слово «loser», поскольку оно стоит меньше, и тогда стоимость посылки будет равна 100+1+5+1=107.

Во втором примере Махмуд не должен совершать никаких замен, поэтому стоимость будет равна 100+1+5+10=116.


Примеры
№Входные данныеВыходные данные
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
 
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
 
116

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++5
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет