Вожди известного племени Мумба-Юмба решили придумать новый боевой вопль для своих воинов. При этом они решили, что вопль должен состоять ровно из \textbf{N} букв (всего в алфавите племени \textbf{M} букв). Также, после долгих исследований было выяснено, что если в вопле встречается слово \textbf{s_i}_\{ \} (слово -- это последовательность букв алфавита, не длиннее трех символов), то этот вопль вселяет во врага \textbf{f_i} единиц страха. Если в вопль входит несколько слов, то их "страшность" суммируется. Например, если вопль содержит слова \textbf{s_i} и \textbf{s_j}, то вопль вселяет \textbf{f_i+f_j} единиц страха. Требуется по заданным \textbf{N}, \textbf{M}, алфавиту и списку слов \textbf{s_i} составить максимально страшный вопль. \InputFile В первой строке записано три числа -- \textbf{N}, \textbf{M} и \textbf{К} (\textbf{0 < N ≤ 100}, \textbf{0 < M < 25}, \textbf{0 ≤ K ≤ 100}), где \textbf{K} -- количество страшных слов. В следующей строке записан алфавит -- строка из M строчных латинских букв. Далее в \textbf{K} строках записана информация о словах -- само слово и через пробел одно число, обозначающее страшность этого слова (\textbf{0 < f_\{i \}≤ 10000}). \OutputFile В выходной файл необходимо вывести страшность полученного вопля.