Во время очередного приключения Диппер нашел строку s длинны n. Он считает, что эта строка является идеальным подарком для Мэйбл. Она привередливая, поэтому не каждая строка ей понравится. К счастью, у Диппера есть знакомый мастер, который умеет изменять строки за определенное количество монет.
Мальчик хочет угодить Мейбл и сделать строку, которая ей понравится, потратив минимальное количество монет. Мастер имеет каталог из m операций замены. Каждая операция позволяет заменить определенный символ a в любой позиции строки на символ b, заплатив c монет. Любую операцию можно использовать неограниченное количество раз в любой позиции строки. Мастер может заменять символы, которые он сам раньше ставил на эту позицию. В каталоге мастера может быть несколько операций изменение a на b с разными стоимостями.
Строка называется k-строкой, если она может быть представлена в виде k копий некоторой строки, записанных подряд. Например, строка «aabaabaabaab» является одновременно 1-строкой, 2-строкой и 4-строкой, но не является 3-строкой, 5-строкой, 6-строкой и так далее. Назовем строку «красивой», если она является k-строкой, для k больше единицы. Мейбл нравятся только красивые строки. Помогите Дипперу понять, может ли он получить красивую строку, а если может, то какое минимальное количество монет ему необходимо потратить на работу мастера.
В первой строке заданы числа n и m — длина строки s и количество операций (2 ≤ n ≤ 105; 1 ≤ m ≤ 105).
Во второй строке задана последовательность маленьких латинских букв длины n — строка s.
Далее следует m строк. В каждой записаны две маленькие латинские буквы a, b и число c — операция, которая соответствует замене символа a на b за цену c (0 ≤ c ≤ 100 000).
Если не существует способа сделать строку s красивой, то выведите -1, иначе выведите количество монет, которое нужно потратить.
6 4
abcdba
d a 3
a z 3
z c 2
a d 1
6
abcdba → dbcdba → dbcdbz → dbcdbc
1) Заменяем букву a на d, заплатив 1.
2) Заменяем букву a на z, заплатив 3.
3) Заменяем букву z на c, заплатив 2.
Ответ: 1 + 3 + 2 = 6
Строка dbcdbc является 2-строкой.