M. Katya and the Broken Keyboard
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Katya was assigned to write an essay, but unfortunately, she realized that some of the keys on her laptop were not always responding.

Through trial and error, she found out that $$$n$$$ keys were broken. Specifically, for each broken key $$$c_i$$$, she determined a number $$$x_i$$$. When pressed for the first time, the key $$$c_i$$$ does not work, then it prints the letter for $$$x_i-1$$$ times, then again does not work once, works again for $$$x_i - 1$$$ times, and so on.

Help Katya find out how many times she will have to press the keys to guarantee that she can write her essay.

Input

The first line is given a string $$$s$$$—the essay Katya wanted to type. The essay consists only of lowercase English letters, and the length of the string does not exceed $$$100\,000$$$.

The second line is given $$$n$$$ ($$$0 \le n \le 26$$$)—the number of broken keys.

The following $$$n$$$ lines contain $$$c_i$$$ and $$$x_i$$$, where $$$c_i$$$ is the broken key, and $$$x_i$$$ ($$$2 \le x_i \le 100$$$) is the frequency of the key's failure to respond. It is guaranteed that $$$c_i$$$ is a lowercase English letter.

Output

Output the minimum number of keystrokes that guarantees Katya will be able to write the essay.

Example
Input
russiaopenhighschoolteamprogrammingcontest
2
s 3
o 5
Output
46