Ashish and Chandu were travelling to Japan. Chandu gave Ashish a weird lottery ticket which had a string S of length N containing lowercase Latin alphabets printed on it. The string corresponded to some number of points and Ashish wanted to maximize his points. All single characters from 'a' to 'z' and all pairs of characters 'aa','ab','ac', ... , 'zx','zy','zz' had value of 1 point. However, there were M special single characters and pairs which had a special value. These characters and pairs had a value greater than or equal to 1.

Ashish realized that in some cases, the string that he got could have more than one score. For example, if he got a string "aab", it could be interpreted in the following ways:
1. a + a + b
2. a + ab
3. aa + b

Each of these ways would give Ashish some points. Help Ashish find out the maximum points that he can get.

Input

First line of input contains 2 integers N and M - the length of the string and the number of special values respectively.
Second line contains a string S of length N, containing lowercase Latin alphabets (a - z)
M lines follow. Each lines consists of 2 space-separated parts. Part 1 is either a single character or a pair of characters, and Part 2 is a positive integer. Part 2 is the special value of Part 1.

Output

Print a single integer - the maximum points scored by Ashish.

Constraints

1 ≤ N ≤ 100000
1 ≤ M ≤ 702
S contains lowercase Latin alphabets between 'a' to 'z' only.
1 ≤ Special value ≤ 100