Emoji

Обмеження: 2 сек., 512 МіБ

Зеник писав Марічці повідомлення у Discord. Щоб додати смайлик, він вводив його назву між двома двокрапками, наприклад :egg:. Проте Discord дав збій і не перетворив ці записи на смайлики.

Тепер Зеник має рядок \(s\) та список назв доступних смайликів. За одну операцію він може вибрати підрядок, що складається з двокрапки, однієї з назв зі списку та ще однієї двокрапки, і замінити весь цей підрядок на відповідний смайлик.

Кожен смайлик вважається одним символом і не бере участі в подальших замінах. Зеник може виконувати операції у довільному порядку або не виконувати їх зовсім.

Допоможіть Зенику та Марічці знайти найменшу можливу довжину повідомлення.

Вхідні дані

У першому рядку задано два цілі числа \(n\) та \(k\) — довжину повідомлення та кількість назв доступних смайликів.

У другому рядку задано рядок \(s\) із \(n\) символів — повідомлення Зеника.

У наступних \(k\) рядках задано по одному непорожньому рядку \(t_i\) — назві смайлика без двокрапок. Назви можуть повторюватися.

Вихідні дані

В єдиному рядку виведіть одне ціле число — найменшу можливу довжину повідомлення після замін.

Обмеження

\(1 \le n, k \le 2 \cdot 10^5\),

\(|s| = n\),

\(|t_i| \ge 1\) для всіх \(1 \le i \le k\),

\(\sum_{i=1}^{k} |t_i| \le 2 \cdot 10^5\),

рядок \(s\) містить лише маленькі латинські літери та символ :,

кожен рядок \(t_i\) містить лише маленькі латинські літери.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
20 2 hi:egg::eggplant:bye egg eggplant	7

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
8 2 :a:bbbb: a bbbb	3

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
14 2 :aaa:aaaa:aaa: aaa aaaa	6

Примітки

У першому прикладі Зеник може замінити :egg: та :eggplant: на смайлики. У повідомленні залишаться hi, два смайлики та bye. Його довжина дорівнюватиме 7.

У другому прикладі достатньо замінити :bbbb: на один смайлик. Перед ним залишаться два символи :a, тому довжина повідомлення дорівнюватиме 3.

У третьому прикладі можна замінити обидва входження :aaa:. Між двома смайликами залишиться aaaa, тому довжина повідомлення дорівнюватиме 6.