I. Increased Intelligence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

As we all know, intelligence is strictly determined by your DNA sequence. One student, Konstantin, at ETHz just realized this recently. He then started reading about what exactly was the reason for intelligence in DNA sequences. He came to the conclusion that there are $$$k$$$ important strings $$$a_1, a_2, \dots, a_k$$$ with strength scores $$$b_1, b_2, \dots, b_k$$$ that make up your IQ-score.

Let $$$L(s)$$$ be the number of times the string $$$s$$$ appears in your DNA sequence as a substring$$$^{*}$$$. Then you can formally define your IQ score as follows.

$$$$$$\sum_{1 \leq i \leq k} L(a_i) \cdot b_i$$$$$$

Excited with this new knowledge, he went straight to a medical center that specializes in DNA modifications. After the doctors did testing on him, they told him the results. Konstantins DNA sequence can be represented as a string of $$$n$$$ characters consisting of letters $$$\{A, C, G, T\}$$$. The doctors told him that there are $$$m$$$ possible indices $$$c_1, c_2, \dots, c_m$$$ in the DNA sequence that can be altered into any other character. Konstantin told the doctors to change his DNA sequence so that his IQ score would be maximum, but they can't possibly solve such a hard problem of maximizing his IQ score. They would need to know how Konstantin wants to change the sequence.

Can you tell Konstantin what the maximum possible IQ score he can have if he changes his DNA sequence optimally?

$$$*$$$ Let $$$a = a_1 a_2 a_3 \dots a_{|a|}$$$ be a string where the $$$i$$$-th character of $$$a$$$ is $$$a_i$$$. We call a string $$$a_l a_{l+1} \dots a_{r}$$$ $$$(1 \leq l \leq r \leq |a|)$$$ a substring of $$$a$$$.

Input

Each test contains multiple test cases.

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 1000)$$$, the number of test cases. The description of the $$$t$$$ test cases follows.

The first line of each test case contains three integers $$$n,m,k$$$ $$$(1 \leq m \leq n \leq 1000; 1 \leq k \leq 100)$$$.

The second line of each test case contains a string s of length $$$n$$$, the DNA sequence of Konstantin.

The next line contains $$$m$$$ integers $$$c_1, c_2, \dots, c_m$$$ $$$(1 \leq c_i \leq n)$$$, the indices of the DNA sequence that can be changed. It is guaranteed that $$$c_i \neq c_j$$$ for $$$i \neq j$$$.

The next $$$k$$$ lines contain a string $$$a_i$$$ $$$(1 \leq |a_i| \leq n)$$$ consisting only of letters from $$$\{A, C, G, T\}$$$ and the strength level $$$b_i$$$ $$$(1 \leq b_i \leq 10^5)$$$ of the $$$i$$$-th string. It is guaranteed that all strings $$$a_i$$$ are unique per test case.

It is guaranteed that over all test cases $$$\sum n \leq 1000$$$, and $$$\sum |a_i| \leq 1000$$$.

Output

For each test case, print a single integer: the highest possible IQ score Konstantin can achieve if his DNA sequence is modified optimally.

Example
Input
1
3 3 2
AAA
1 2 3
CC 5
AA 3
Output
10