405545: GYM101991 E Exciting Menus

In a restaurant, given N menus, where the menus are represented by the strings S¹, ..., S^N. Each string Sⁱ is associated with an array Aⁱ (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:

• Sⁱ_j, k =  The substring [j, k] (where j, k are one-based, inclusive) of the string Sⁱ.
• number of menus (from S¹, ..., S^N) that contain the submenu-string Sⁱ_j, k as a prefix.
• |Sⁱ_j, k| is the size of the submenu, which is the length of the substring representing the submenu.
• Aⁱ_k 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 ≤ 10⁵) specifying the number of menus in the restaurant.

Then N lines follow, the i^th line contains a string Sⁱ representing the i^th menu. All the menus are non-empty strings consisting of lowercase English letters, and the sum of their lengths will not exceed 10⁵ per test case.

Then N lines follow, the i^th line contains array Aⁱ, in which Aⁱ has the same length as string Sⁱ and (0 ≤ Aⁱ_k ≤ 10⁹). 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).