Вопль
Вожді відомого племені Мумба-Юмба вирішили створити новий бойовий крик для своїх воїнів. Вони постановили, що крик має складатися рівно з N букв (в алфавіті племені є M букв). Після тривалих досліджень з'ясувалося, що якщо в крику зустрічається слово s_i (слово — це послідовність букв алфавіту, не довше трьох символів), то цей крик вселяє у ворога f_i одиниць страху. Якщо в крику є кілька таких слів, їх "страшність" сумується. Наприклад, якщо крик містить слова s_i і s_j, то крик вселяє f_i+f_j одиниць страху.
Необхідно, маючи задані N, M, алфавіт і список слів s_i, скласти максимально страшний крик.
Вхідні дані
У першому рядку записано три числа — N, M і K (0 < N ≤ 100, 0 < M < 25, 0 ≤ K ≤ 100), де K — кількість страшних слів. У наступному рядку записано алфавіт — рядок з M малих латинських букв. Далі в K рядках подано інформацію про слова — саме слово і через пробіл одне число, що позначає страшність цього слова (0 < f_{i} ≤ 10000).
Вихідні дані
У вихідний файл необхідно вивести страшність отриманого крику.