Problem 1: Genetic Code

The genetic code hides the secrets of life and its historical evolution. Once the genetic code of an organism is deciphered, modern molecular "gene scissors" technology can be used to cut and assemble gene sequences, allowing us to further reveal the secrets of life through observation and experimentation. A gene sequence is the primary structure of a DNA molecule carrying genetic information, represented by a string of letters from $\{A, C, G, T\}$.

A gene sequence is typically represented as $X = x_1 x_2 \dots x_n$, where $x_i \in \{A, C, G, T\}$ and $1 \le i \le n$. A substring $x_i, x_{i+1}, \dots, x_j$ of a gene sequence $X$ is called the $(i, j)$ segment of $X$. Gene sequence cutting and assembly experiments in modern biological laboratories require first determining a target gene sequence $S$, and then selecting several gene samples from the laboratory's gene bank. The target gene sequence $S$ is obtained by cutting and assembling these gene samples.

Generally, the cutting and assembly experiment requires two steps:

(1) Cutting: Take a sample $T = t_1 t_2 \dots t_n$ of a certain gene from the gene bank and cut it at position $k$ to obtain two gene segments $(1, k)$ and $(k+1, n)$, where $1 \le k < n$. Select one of these segments as material for the next assembly step. When $k=n$, it means no cutting is required. Multiple samples of the same gene can be taken from the gene bank, and the cut gene segments can be identical, but each cut gene segment can only be used once during assembly.

(2) Assembly: Use the gene segments selected during the cutting phase to assemble the target gene sequence $S$ in a certain order.

For example, let $S = CACAACACA$. The available gene sequences are: $T_1 = CACA$, $T_2 = CAA$, $T_3 = ACC$. Taking 1 gene sample $T_1 = CACA$, cutting the $(3, 3)$ segment $A$ from gene sample $T_2 = CAA$, and cutting two $(1, 2)$ segments $AC$ from 2 gene samples $T_3 = ACC$, we can assemble the target gene sequence $S = CACAACACA$.

The costs associated with using different gene samples generally differ. In the example above, if the costs for using gene samples $T_1, T_2,$ and $T_3$ are $3, 10,$ and $2$ respectively, the cost of the above gene assembly experiment is $17$. For the same target gene sequence $S$, there are often multiple cutting and assembly schemes. The scheme with the minimum total cost is the optimal scheme. In the example above, if we take 2 samples of $T_1$ and 1 $(1, 1)$ segment $A$ from $T_3$, $S = CACAACACA$, the required cost is $8$. This is an optimal assembly scheme.

Genetic Code Problem: Given a target gene sequence $S$ and $n$ types of available gene sequences $T_1, T_2, \dots, T_n$, with corresponding costs $c_1, c_2, \dots, c_n$ for the gene samples, design an optimal scheme to assemble the target gene sequence $S$ such that the total cost is minimized.

Input

The input contains multiple test cases. The first line contains a positive integer $k$, representing the number of test cases.

For each test case: The first line contains a string $S$, representing the target gene sequence. The second line contains a positive integer $n$, representing the number of available gene sequences. The following $n$ lines each contain a string $T_i$ and a positive integer $c_i$, separated by a space, representing a gene sequence and its cost.

Output

For each test case, output the minimum total cost required to assemble the target gene sequence $S$ on a single line. If it is impossible to assemble the target gene sequence $S$, output $-1$.

Examples

Input 1

1
CACAACACA
3
CACA 3
CAA 10
ACC 2

Output 1

8

Constraints

Let $A$ be the length of the target gene sequence, $B$ be the sum of the lengths of all gene samples, and $C$ be the maximum cost of a gene sample.

• 10% of the test data satisfies $A \le 1000, B \le 1000$.
• 30% of the test data satisfies $A \le 10000, B \le 10000$.
• 100% of the test data satisfies $A \le 300000, B \le 300000, C \le 10^9$.