Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

In Chefland, each citizen has their own personal string. Chef is no exception. Recently, his string broke and he went to a shop to get a new one.

There are two strings in the shop: $A$ and $B$. Chef may choose any substring $A_{s}$ of $A$ (possibly empty) and any substring $B_{s}$ of $B$ (also possibly empty). Then, the shop assistant cuts these substrings out and sells a single string $C = A_{s} + B_{s}$ (here, $+$ denotes string concatenation) to Chef. For example, if $A$ is "aba" and $B$ is "cde", then some of the strings Chef can buy are "ba", "bac", "bacd", "ae", "d", "acde", "aba", "cde" or "abacde".

Chef has seen a lot of strings in his life and he liked exactly $N$ of them (numbered $1$ through $N$). For each valid $i$, the $i$-th of these strings is denoted by $S_{i}$ and according to Chef, it has a beauty $b_{i}$. Let's denote the number of substrings of $C$ that are equal to $S_{i}$ by $cnt_{i}(C)$. If Chef buys a string $C$, he says that the pleasure he gets from this string is $\sum_{i=1}^N cnt_{i}(C) \cdot b_{i}$.

What is the maximum possible pleasure Chef can get from a string he buys in the shop?

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single string $A$.
The second line contains a single string $B$.
The third line contains a single integer $N$.
The following $N$ lines describe Chef's favourite strings. For each valid $i$, the $i$-th of these lines contains a string $S_{i}$, followed by a space and an integer $b_{i}$.

------ Output ------
For each test case, print a single line containing one integer ― the maximum pleasure.

------ Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ |A|, |B| ≤ 10^{3}$
$1 ≤ N ≤ 10^{4}$
$1 ≤ |S_{i}| ≤ 26$ for each valid $i$
$1 ≤ b_{i} ≤ 10^{5}$ for each valid $i$
$A, B, S_{1}, S_{2}, \ldots, S_{N}$ contain only lowercase English letters
$S_{1}, S_{2}, \ldots, S_{N}$ are pairwise distinct
the sum of $|A|$ over all test cases does not exceed $2 \cdot 10^{3}$
the sum of $|B|$ over all test cases does not exceed $2 \cdot 10^{3}$
the sum of $N$ over all test cases does not exceed $2 \cdot 10^{4}$

------ Subtasks ------
Subtask #1 (20 points, time limit 2 seconds): $|A|, |B|, N ≤ 100$

Subtask #2 (30 points, time limit 1 second):
the sum of $|A|$ over all test cases does not exceed $500$
the sum of $|B|$ over all test cases does not exceed $500$

Subtask #3 (50 points, time limit 1 second): original constraints

----- Sample Input 1 ------
1

hitech

codechef

3

chef 3

code 1

eche 5
----- Sample Output 1 ------
13
----- explanation 1 ------
Example case 1: Chef can buy the string $C$ = "tech" + "echef" = "techechef". In this string $C$, one substring is "chef", there are no substrings "code" and two substrings are "eche". Chef's pleasure in this case is $1 \cdot 3 + 0 \cdot 1 + 2 \cdot 5 = 13$, which is the maximum possible pleasure.

见题面

见题面