Вожді відомого племені Мумба-Юмба вирішили вигадати новий бойовий крик для своїх воїнів. При цьому вони вирішили, що крик повинен складатися з \(N\) букв (всього в алфавіті племені \(M\) букв). Також, після довгих досліджень було з'ясовано, що й у крику зустрічається слово \(s_i\) (слово - це послідовність букв алфавіту, не довше трьох символів), цей крик вселяє у ворога \(f_i\) одиниць страху. Якщо у крик входить кілька слів, їх "страшність" підсумовується. Наприклад, якщо крик містить слова \(s_i\) та \(s_j\), то крик вселяє \(f_i+f_j\) одиниць страху.

Потрібно по заданим \(N, M\), алфавіту та списку слів \(s_i\) скласти максимально страшний крик.

Формат вхідних даних

У першому рядку записано три числа - \(N, M\) і \(К\) (\(1 ≤ N ≤ 100\), \(1 ≤ M ≤ 24\), \(0 ≤ K ≤ 100\)), де \(K\) — кількість страшних слів.

У наступному рядку записаний алфавіт - рядок з \(M\) малих латинських букв.

Далі в \(K\) рядках записана інформація про слова - саме слово і через пропуск одне число, що позначає страшність цього слова (\(1 ≤ f_i ≤ 10000\)).

Формат вихідних даних

У вихідний файл необхідно вивести страшність отриманого крику і на наступному рядку - сам крик.

Приклад вхідних даних

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

Приклад вихідних даних

16
abe