Exciting Menus

A restaurant has $N$ menus, given as the strings $S^1, \dots , S^N$. Each string $S^i$ comes with an array $A^i$ of joy levels of the same length. In this problem you choose a submenu defined by three integers $(i, j, k)$, where $i$ is the index of a menu and $j, k$ specify a substring of that menu.

Find the submenu of the highest quality, where the quality $Q$ is defined by

$Q(i, j, k) = \text{popularity}(S^i_{j,k}) \cdot A^i_k \cdot |S^i_{j,k}|$

• $S^i_{j,k}$ = the substring $[j, k]$ of the string $S^i$ (with $j, k$ one-based and inclusive).
• popularity($S^i_{j,k}$) = the number of menus among $S^1, \dots , S^N$ that contain the submenu string $S^i_{j,k}$ as a prefix.
• $|S^i_{j,k}|$ is the size of the submenu, the length of the substring that represents it.
• $A^i_k$ is the joy level of the submenu (the $k$-th entry of the $i$-th array). Note that the index $j$ is not used here.

Can you find the submenu of the highest quality? Output the maximum value of the function $Q$.

The first line of the input contains a single integer $T$, the number of test cases.

Each test case begins with a line containing an integer $N$ ($1 \le N \le 10^5$), the number of menus in the restaurant.

Then $N$ lines follow. The $i$-th line contains a string $S^i$ representing the $i$-th menu. All menus are nonempty strings of lowercase English letters, and the sum of their lengths does not exceed $10^5$ per test case.

Then $N$ lines follow. The $i$-th line contains the array $A^i$, which has the same length as the string $S^i$, with $0 \le A^i_k \le 10^9$. The values of each array are space-separated.

For each test case, print a single line containing an integer $Q$, the maximum quality over the best submenu $(i, j, k)$.

The triples corresponding to the answers of the two given cases are $(1, 1, 5)$ and $(1, 4, 5)$.