Problems
Cry
Cry
Вожді відомого племені Мумба-Юмба вирішили придумати новий бойовий вопль для своїх воінів. При цьому вони вирішили, що вопль повинен складатись рівно з \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
У вихідний файл необхідно вивести страшність отриманого вопля.
Input example #1
3 5 4 abcde abc 10 ab 5 be 7 e 4
Output example #1
16