Your final exam is tomorrow and you need to study, fast! Sadly, you don't know if the book you've borrowed from the library is worth reading.

To figure this out, you'll search for some number of keywords in your book. Each keyword has some amount of "utility". For example, if your book has the content:

ACCORDINGTOALLKNOWNLAWSOFAVIATIONTHEREISNOWAYABEESHOULDBEABLETOFLY

and your keywords are:

• CORD: ~10~ utility
• TO: ~5~ utility
• KNOW: ~20~ utility
• NOW: ~10~ utility
• SNOW: ~30~ utility

then your book has a total "utility" of ~10 + 5 + 5 + 20 + 10 + 10 + 30 = 90~, because:

• CORD appears ~1~ time
• TO appears ~2~ times
• KNOWN appears ~1~ time
• NOW appears ~2~ times
• SNOW appears ~1~ time

Note that keywords can overlap. Given a book's content, what is the total amount of "utility" that book has?

Input

The first line of each test case contains ~T~ ~(1 \leq T.\text{length} \leq 10^5)~, the content of your book, as one long string of uppercase characters.

The next line of each test case contains an integer ~n~ ~(1 \leq N \leq 1000)~, the number of keywords you have to search for in your book.

The next ~m~ lines of each input are in the form ~S \; k~, indicating that keyword ~S~ ~(1 \leq S.\text{length} \leq 1000)~ has ~k~ ~(1 \leq k \leq 10^8)~ utility.

Note: Each keyword is guaranteed to be unique.

Output

Output the total utility of your book.

Example

Input

ACCORDINGTOALLKNOWNLAWSOFAVIATIONTHEREISNOWAYABEESHOULDBEABLETOFLY
5
CORD 10
TO 5
KNOW 20
NOW 10
SNOW 30

Output

90

See above for this example.

Input

AAABABABAAABAA
4
AA 5
AAB 10
BABA 30
AAA 5

Output

115

• AA appears in the book ~5~ times.
• AAB appears in the book ~2~ times.
• BABA appears in the book ~2~ times.
• AAA appears in the book ~2~ times.

Therefore, the total utility of the book is ~5 \times 5 + 10 \times 2 + 30 \times 2 + 5 \times 2 = 25 + 20 + 60 + 10 = 115~.