시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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)$.

예제 입력 1

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

예제 출력 1

500
600

힌트

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