Problem Description

Given a string \( S \) and a set of words \( P = \{P_1, P_2, \ldots, P_M\} \) with \( M \) elements. Each word \( P_i \) has an integer weight \( W_i \).

Consider extracting words from the string \( S \) that are in the set \( P \) without overlapping. What is the maximum sum of the weights of the extracted words?

Note that if the same word is extracted multiple times, each occurrence is counted separately.

Input Format

The input is given from the standard input in the following format:

\( S \) \( M \) \( P_1 \) : \( P_M \) \( W_1 \) : \( W_M \)

Output Format

Output the maximum sum of the weights of the words in one line.

Sample Input and Output

Sample Input #1

abcabcabc
3
ab
bc
ca
1
1
1

Sample Output #1

4

Sample Input #2

abracadabra
4
b
abra
cad
rac
1
10
50
100

Sample Output #2

111

Sample Input #3

abcd
2
ad
bc
1192
794

Sample Output #3

794

Notes/Hints

Constraints

• \( 1 \leq |S| \leq 200000 \)
• \( 1 \leq M \leq 5000 \)
• \( 1 \leq |P_i| \leq 200 \)
• \( 1 \leq W_i \leq 10000 \)
• \( S \) and \( P_i \) are strings consisting of lowercase English letters.

见题面 Input 部分

见题面 Output 部分