Score : $625$ points

问题陈述

给定 $N$ 个字符串 $S_1, S_2, \ldots, S_N$，它们由小写英文字母组成，以及 $N$ 个正整数 $A_1, A_2, \ldots, A_N$。

如果集合 $T$ 是 $\lbrace 1, 2, \ldots, N \rbrace$ 的一个子集，并且对于 $T$ 中的任意两个不同的元素 $i, j$，$S_i$ 不是 $S_j$ 的子串，则称 $T$ 为一个好集合。

找出一个好集合 $T$ 的 $\displaystyle \sum_{i \in T} A_i$ 的最大可能值。

什么是子串？字符串 $S$ 的一个子串是通过从 $S$ 的开头删除零个或多个字符，以及从 $S$ 的结尾删除零个或多个字符得到的字符串。例如，ab 是 abc 的一个子串，但 ac 不是 abc 的子串。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given $N$ strings $S_1, S_2, \ldots, S_N$ consisting of lowercase English letters and $N$ positive integers $A_1, A_2, \ldots, A_N$.

A subset $T$ of $\lbrace 1, 2, \ldots, N \rbrace$ is called a good set if there is no pair $i, j \in T (i \neq j)$ such that $S_i$ is a substring of $S_j$.

Find the maximum possible value of $\displaystyle \sum_{i \in T} A_i$ for a good set $T$.

What is a substring? A substring of a string $S$ is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of $S$. For example, ab is a substring of abc, but ac is not a substring of abc.

Constraints

• $1 \leq N \leq 100$
• $S_i$ is a string consisting of lowercase English letters.
• $1 \leq |S_i|$
• $|S_1| + |S_2| + \ldots + |S_N| \leq 5000$
• $1 \leq A_i \leq 10^9$

Input

The input is given from Standard Input in the following format:

$N$

$S_1$

$S_2$

$\vdots$

$S_N$

$A_1$ $A_2$ $\ldots$ $A_N$

Output

Print the answer.

Sample Input 1

4
atcoder
at
coder
code
5 2 3 4

Sample Output 1

6

The possible good sets $T$ and their corresponding $\displaystyle \sum_{i \in T} A_i$ are as follows:

• $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$

The maximum among them is $6$, so print $6$.

Sample Input 2

10
abcd
abc
ab
a
b
c
d
ab
bc
cd
100 10 50 30 60 90 80 70 40 20

Sample Output 2

260