Вожди известного племени Мумба-Юмба решили придумать новый боевой вопль для своих воинов. При этом они решили, что вопль должен состоять ровно из N букв (всего в алфавите племени M букв). Также, после долгих исследований было выяснено, что если в вопле встречается слово s
i (слово – это последовательность букв алфавита, не длиннее трех символов), то этот вопль вселяет во врага f
i единиц страха. Если в вопль входит несколько слов, то их “страшность” суммируется. Например, если вопль содержит слова s
i и s
j, то вопль вселяет f
i+f
j единиц страха.
Требуется по заданным N, M, алфавиту и списку слов s
i составить максимально страшный вопль.
Входные данные:
В первой строке записано три числа – N, M и К (0<N≤100, 0<M<25, 0 ≤ K ≤ 100), где K – количество страшных слов. В следующей строке записан алфавит – строка из M строчных латинских букв. Далее в K строках записана информация о словах – само слово и через пробел одно число, обозначающее страшность этого слова (0 < f
i ≤ 10000).
Выходные данные:
В выходной файл необходимо вывести страшность полученного вопля и на следующей строке – сам вопль.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3 5 4
abcde
abc 10
ab 5
be 7
e 4 |
16
abe |