28937번 - Подарок Диппера 다국어

문제

Во время очередного приключения Диппер нашел строку $s$ длинны $n$. Он считает, что эта строка является идеальным подарком для Мэйбл. Она привередливая, поэтому не каждая строка ей понравится. К счастью, у Диппера есть знакомый мастер, который умеет изменять строки за определенное количество монет.

Мальчик хочет угодить Мейбл и сделать строку, которая ей понравится, потратив минимальное количество монет. Мастер имеет каталог из $m$ операций замены. Каждая операция позволяет заменить определенный символ $a$ в любой позиции строки на символ $b,ドル заплатив $c$ монет. Любую операцию можно использовать неограниченное количество раз в любой позиции строки. Мастер может заменять символы, которые он сам раньше ставил на эту позицию. В каталоге мастера может быть несколько операций изменение $a$ на $b$ с разными стоимостями.

Строка называется $k$-строкой, если она может быть представлена в виде $k$ копий некоторой строки, записанных подряд. Например, строка <<aabaabaabaab>> является одновременно 1ドル$-строкой, 2ドル$-строкой и 4ドル$-строкой, но не является 3ドル$-строкой, 5ドル$-строкой, 6ドル$-строкой и так далее. Назовем строку <<красивой>>, если она является $k$-строкой, для $k$ больше единицы. Мейбл нравятся только красивые строки. Помогите Дипперу понять, может ли он получить красивую строку, а если может, то какое минимальное количество монет ему необходимо потратить на работу мастера.

입력

В первой строке заданы числа $n$ и $m$ --- длина строки $s$ и количество операций (2ドル \le n \le 10^5$; 1ドル \le m \le 10^5$).

Во второй строке задана последовательность маленьких латинских букв длины $n$ --- строка $s$.

Далее следует $m$ строк. В каждой записаны две маленькие латинские буквы $a,ドル $b$ и число $c$ --- операция, которая соответствует замене символа $a$ на $b$ за цену $c$ (0ドル \le c \le 100,000円$).

출력

Если не существует способа сделать строку $s$ красивой, то выведите -1, иначе выведите количество монет, которое нужно потратить.

제한

노트

abcdba $\to$ dbcdba $\to$ dbcdbz $\to$ dbcdbc

1. Заменяем букву a на d, заплатив 1.
2. Заменяем букву a на z, заплатив 3.
3. Заменяем букву z на c, заплатив 2.

Ответ: 1 + 3 + 2 = 6

Строка dbcdbc является 2-строкой.