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.

Difficulty: VERY_HARD
Tags: String algorithms

Data structures

Range queries
Skill types: Data structures

Range queries

Starter code:

Solutions:
from sys import stdin, stdout
T = int(stdin.readline())

def presuf(pre, suf):
	for s in bts:
		for i in range(len(s) - 1):
			(pre[s[:i + 1]], suf[s[len(s) - i - 1:]]) = (True, True)
	return (pre, suf)
for _ in range(T):
	a = stdin.readline().strip('\n')
	na = len(a)
	b = stdin.readline().strip('\n')
	nb = len(b)
	A = [0] * (na + 1)
	B = [0] * (nb + 1)
	(n, bts, AB) = (int(stdin.readline()), {}, [[0 for i in range(nb + 1)] for j in range(na + 1)])
	for i in range(n):
		(s, bt) = stdin.readline().split(' ')
		bt = int(bt)
		bts[s] = bt
	(pre, suf) = presuf({}, {})
	As = {}
	done = {}
	for k in range(min(26, na), 0, -1):
		for i in range(na, k - 1, -1):
			s = a[i - k:i]
			if s in bts:
				A[i] += bts[s]
			if s not in pre:
				continue
			if i in done:
				del pre[s]
				continue
			for j in range(k):
				if s[k - j - 1:] not in As:
					As[s[k - j - 1:]] = []
				As[s[k - j - 1:]].append(i)
				done[i] = True
			del pre[s]
	(Bs, done, mx) = ({}, {}, 0)
	for k in range(min(26, nb), 0, -1):
		for i in range(nb - k + 1):
			s = b[i:i + k]
			if s in bts:
				B[i + 1] += bts[s]
			if s not in suf:
				continue
			if i in done:
				del suf[s]
				continue
			for j in range(k):
				if s[:j + 1] not in Bs:
					Bs[s[:j + 1]] = []
				Bs[s[:j + 1]].append(i + 1)
				done[i] = True
			del suf[s]
	for i in range(1, na + 1, 1):
		A[i] = A[i] + A[i - 1]
	for i in range(nb - 1, -1, -1):
		B[i] = B[i] + B[i + 1]
	for s in bts:
		for i in range(1, len(s)):
			st = s[:i]
			en = s[i:]
			bt = bts[s]
			if st in As and en in Bs:
				for x in As[st]:
					for y in Bs[en]:
						AB[x][y] += bt
	for i in range(na + 1):
		for j in range(nb + 1):
			mx = max(A[i] + B[j] + AB[i][j], mx)
	print(mx)