在一家餐厅中，给定 $N$ 个菜单，这些菜单由字符串 $S^1, \dots, S^N$ 表示。每个字符串 $S^i$ 都关联有一个长度相同的快乐值数组 $A^i$。在本题中，你需要选择一个由三个整数 $(i, j, k)$ 定义的子菜单，其中 $i$ 是某个菜单的索引，$j$ 和 $k$ 指定了该菜单的一个子串。

我们需要找到质量最高的子菜单，其中质量 $Q$ 由以下函数定义：

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

• $S^i_{j,k}$：字符串 $S^i$ 的子串 $[j, k]$（其中 $j, k$ 为从 1 开始的索引，包含边界）。
• $\text{popularity}(S^i_{j,k})$：在 $S^1, \dots, S^N$ 中，以 $S^i_{j,k}$ 为前缀的菜单数量。
• $|S^i_{j,k}|$：子菜单的大小，即表示该子菜单的子串长度。
• $A^i_k$：子菜单的快乐值（第 $i$ 个数组的第 $k$ 个元素），请注意这里不使用索引 $j$。

你能找到质量最高的子菜单吗？请输出函数 $Q$ 对应的最高质量。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $N$ ($1 \le N \le 10^5$)，表示餐厅中菜单的数量。

接下来 $N$ 行，第 $i$ 行包含一个字符串 $S^i$，表示第 $i$ 个菜单。所有菜单均为由小写英文字母组成的非空字符串，且每个测试用例中所有字符串长度之和不超过 $10^5$。

接下来 $N$ 行，第 $i$ 行包含数组 $A^i$，其中 $A^i$ 的长度与字符串 $S^i$ 相同，且满足 $0 \le A^i_k \le 10^9$。数组中的值以空格分隔。

输出格式

对于每个测试用例，打印一行包含一个整数 $Q$，表示对应最佳子菜单 $(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

说明

两个给定案例对应的三元组分别为 $(1, 1, 5)$ 和 $(1, 4, 5)$。