AT_abc354_g [ABC354G] Select Strings

有 $N$ 个仅由小写英文字母组成的字符串 $S_1,S_2,\ldots,S_N$，以及 $N$ 个正整数 $A_1,A_2,\ldots,A_N$。 对于集合 $\lbrace 1,2,\ldots,N \rbrace$ 的某个子集 $T$，如果对于任意 $i,j \in T$ 且 $i \neq j$，都不存在 $S_i$ 是 $S_j$ 的子串的情况，则称 $T$ 为**好集合**。 请你选择一个好集合 $T$，使得 $\displaystyle\sum_{i\in T}A_i$ 的值最大，并输出这个最大值。 子串的定义：字符串 $S$ 的**子串**是指通过从 $S$ 的开头删除 $0$ 个或多个字符、从结尾删除 $0$ 个或多个字符后得到的字符串。例如，`ab` 是 `abc` 的子串，但 `ac` 不是 `abc` 的子串。

输入按以下格式从标准输入读入。 > $N$ > $S_1$ > $S_2$ > $\vdots$ > $S_N$ > $A_1\ A_2\ \ldots\ A_N$

请输出答案。

## 限制条件 - $1 \leq N \leq 100$ - $S_i$ 由小写英文字母组成 - $1 \leq |S_i|$ - $|S_1|+|S_2|+\ldots+|S_N| \leq 5000$ - $1 \leq A_i \leq 10^9$ ## 样例解释 1 作为好集合的 $T$ 及其对应的 $\displaystyle\sum_{i\in T}A_i$ 如下： - 当 $T = \lbrace 1 \rbrace$ 时，$\displaystyle\sum_{i\in T}A_i = 5$ - 当 $T = \lbrace 2 \rbrace$ 时，$\displaystyle\sum_{i\in T}A_i = 2$ - 当 $T = \lbrace 3 \rbrace$ 时，$\displaystyle\sum_{i\in T}A_i = 3$ - 当 $T = \lbrace 4 \rbrace$ 时，$\displaystyle\sum_{i\in T}A_i = 4$ - 当 $T = \lbrace 2,3 \rbrace$ 时，$\displaystyle\sum_{i\in T}A_i = 5$ - 当 $T = \lbrace 2,4 \rbrace$ 时，$\displaystyle\sum_{i\in T}A_i = 6$ 其中最大值为 $6$，因此输出 $6$。 由 ChatGPT 4.1 翻译