Лето 7

Вожди известного племени Мумба-Юмба решили придумать новый боевой вопль для своих воинов. При этом они решили, что вопль должен состоять ровно из `N` букв (всего в алфавите племени `M` букв). Также, после долгих исследований было выяснено, что если в вопле встречается слово `s_i` (слово – это последовательность букв алфавита, не длиннее трех символов), то этот вопль вселяет во врага `f_i` единиц страха. Если в вопль входит несколько слов, то их "страшность" суммируется. Например, если вопль содержит слова `s_i` и `s_j`, то вопль вселяет `f_i\ +\ f_j` единиц страха. Если вопль содержит `k` экземпляров одного и того же `i`-го слова, то этот вопль вселяет `k⋅f_i` единиц страха.

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

В первой строке записано три числа – `N`, `M` и `K\ (0\ <\ N\ ≤\ 100,\ 0\ <\ M\ <\ 25,\ 0\ ≤\ K\ ≤\ 100)`, где `K` – количество страшных слов. В следующей строке записан алфавит – строка из `M` строчных латинских букв. Далее в `K` строках записана информация о словах – само слово и через пробел одно число `f_i\ (0\ <\ f_i\ ≤\ 10000)`, обозначающее страшность этого слова.

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

3 5 4
abcde
abc 10
ab 5
be 7
e 4

16
abe