18708번 - Exciting Menus 다국어

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

$$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]$ (where $j, k$ are one-based, inclusive) of the string $S^i$.
• popularity($S^i_{j,k}$) = number of menus (from $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, which is the length of the substring representing the submenu.
• $A^i_k$ is the joy level of the submenu ($k$^th entry of the $i$^th 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 \le N \le 10^5$) specifying 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 the menus are nonempty strings consisting of lowercase English letters, and the sum of their lengths will not exceed $10^5$ per test case.

Then $N$ lines follow, the $i$^th line contains array $A^i$, in which Ai has the same length as string $S^i$ and ($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$ representing the maximum quality corresponding to 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)$.