In a restaurant, given N menus, where the menus are represented by the strings S1, ..., SN. Each string Si is associated with an array Ai (of the same length) of joy levels. In this problem, you should choose a submenu defined by three integers (i, j, k), where i is the index of one of the menus, and j, k specify a substring of this chosen menu.
We need to find the submenu of the highest quality, where the quality Q is defined by the function:
- Sij, k = The substring [j, k] (where j, k are one-based, inclusive) of the string Si.
-
number of menus (from S1, ..., SN) that contain the submenu-string Sij, k as a prefix. - |Sij, k| is the size of the submenu, which is the length of the substring representing the submenu.
- Aik is the joy level of the submenu (
entry of the 
array), please note that the index j is not used here.
Can you find the submenu of the highest quality? Please output the corresponding highest quality of the function Q.
The first line of the input contains a single integer T specifying the number of test cases.
Each test case begins with a line containing an integer N (1 ≤ N ≤ 105) specifying the number of menus in the restaurant.
Then N lines follow, the ith line contains a string Si representing the ith menu. All the menus are non-empty strings consisting of lowercase English letters, and the sum of their lengths will not exceed 105 per test case.
Then N lines follow, the ith line contains array Ai, in which Ai has the same length as string Si and (0 ≤ Aik ≤ 109). The values of each array are space-separated.
For each test case, print a single line containing an integer Q representing the maximum quality corresponding to the best submenu (i, j, k).
2
2
aabaa
aa
0 0 0 0 100
0 1
4
bbbaa
aa
aab
aax
0 0 0 0 100
0 0
0 0 0
0 0 0
500
600
The triples corresponding to the answers of the two given cases are (1, 1, 5) and (1, 4, 5).
