Вожді відомого племені Мумба-Юмба вирішили придумати новий бойовий вопль для своїх воінів. При цьому вони вирішили, що вопль повинен складатись рівно з 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).
У вихідний файл необхідно вивести страшність отриманого вопля.