Toxicity Check

You are given a main string S and a list of toxic subsequences, each associated with a toxicity value. For each test case, compute the total toxicity by counting the number of non-overlapping occurrences of each toxic subsequence in S and multiplying the count by its toxicity value. If the sum of these products is greater than a given threshold, print YES, otherwise print NO.

Mathematically, if there are toxic subsequences \( {s_i, t_i} \) (where \( s_i \) is the subsequence and \( t_i \) its toxicity) in the main string \( S \), let \( c_i \) be the count of non-overlapping occurrences of \( s_i \) in \( S \). Then the total toxicity is computed as:

\( \text{total} = \sum_{i} c_i \times t_i \)

If \( \text{total} > \text{threshold} \), the answer is YES, otherwise NO.

inputFormat

The first line contains an integer T, the number of test cases. Each test case is described as follows:

1. A line containing the main string S.
2. A line containing an integer N, the number of toxic subsequences.
3. The next N lines each contain a toxic subsequence and its toxicity value (an integer), separated by a space.
4. A line containing an integer, the threshold.

All input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing either YES if the total toxicity is greater than the threshold, or NO otherwise. The outputs of all test cases should be printed to standard output (stdout), each on a separate line.

## sample

4
aaabbbcccc
2
aa 3
bb 4
5
gggtttcccaa
3
ggg 2
ttt 3
ccc 5
10
abcdefgh
0
1
aaabbbccc
3
aa 3
bb 4
cc 2
1

YES
NO
NO
YES

</p>