Emoji

Limits: 2 sec., 512 MiB

Zenyk was writing a message to Marichka on Discord. To add an emoji, he typed its name between two colons, for example :egg:. However, Discord glitched and did not turn these entries into emojis.

Now Zenyk has a string \(s\) and a list of the names of the available emojis. In one operation he can choose a substring made of a colon, one of the names from the list and another colon, and replace this whole substring with the corresponding emoji.

Each emoji counts as one character and takes no part in further replacements. Zenyk may perform the operations in any order, or not perform any at all.

Help Zenyk and Marichka find the smallest possible length of the message.

Input

The first line contains two integers \(n\) and \(k\) – the length of the message and the number of available emoji names.

The second line contains a string \(s\) of \(n\) characters – Zenyk’s message.

Each of the next \(k\) lines contains one non-empty string \(t_i\) – the name of an emoji, without colons. Names may repeat.

Output

Print one integer – the smallest possible length of the message after the replacements.

Constraints

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

\(|s| = n\),

\(|t_i| \ge 1\),

\(|t_1| + |t_2| + \ldots + |t_k| \le 2 \cdot 10^5\),

the string \(s\) consists only of lowercase Latin letters and the character :,

each string \(t_i\) consists only of lowercase Latin letters.

Samples

Input (stdin) сopy	Output (stdout) сopy
20 2 hi:egg::eggplant:bye egg eggplant	7

Input (stdin) сopy	Output (stdout) сopy
8 2 :a:bbbb: a bbbb	3

Input (stdin) сopy	Output (stdout) сopy
14 2 :aaa:aaaa:aaa: aaa aaaa	6

Notes

In the first example, Zenyk can replace :egg: and :eggplant: with emojis. The message then keeps hi, two emojis and bye, so its length is 7.

In the second example, it is enough to replace :bbbb: with one emoji. Two characters, :a, remain in front of it, so the length of the message is 3.

In the third example, both occurrences of :aaa: can be replaced. The string aaaa remains between the two emojis, so the length of the message is 6.