<ПРЕД Задача:
СЛЕД>
Задачу решили 194 пользователя: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Вопль

Time limit = 4

Вожди племени Мумба-Юмба решили придумать новый боевой вопль для своих воинов. При этом они решили, что вопль должен состоять ровно из N букв (всего в алфавите M букв).

После долгих исследований было выяснено, что если в вопле встречается слово si, то страшность слова увеличивается на fi, причем учитывается каждое вхождение слова.

Требуется по заданным M, N и списку страшных слов составить максимально страшный вопль.

Вход Первая строчка содержит три числа — N, M и K. ( 1 ≤ N ≤ 100, 1 ≤ M ≤ 25, 1 < K ≤ 100 ), где K — количество различных страшных слов. В следующей строчке записан алфавит — строка из M маленьких латинских букв. Далее в K строчках следует информация о страшных словах — в каждой строчке страшное слово si и через пробел его страшность fi (точнее не страшность, а величина страшности, которую данная комбинация букв вносит в страшность вопля, страшность слова si может быть страшнее fi).

Страшность — это натуральное число меньше 10000. Эталонные страшные слова во входе не повторяются.

Выход Необходимо вывести максимальную страшность и один из максимально страшных воплей на следующей строчке.

Вход#1
4 3 4
abc
a 1
b 1
ab 3
caa 6
Выход#1
12
caab

Вход#2
7 10 4
abcdefghij
a 1
b 1
ab 4
bac 8
Выход#2
25
bacabac

Автор:
Задача с Московской школьной городской олимпиады по программированию (несколько модифицированная)
декабрь 2002

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 3.81.28.10