选择字符串

题目描述

给你 $N$ 个由小写英文字母组成的字符串 $S_1, S_2, \ldots, S_N$ 和 $N$ 个正整数 $A_1, A_2, \ldots, A_N$。

若集合 $T \subseteq \lbrace 1, 2, \ldots, N \rbrace$ 中不存在 $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$

输出格式

输出答案。

样例

4
atcoder
at
coder
code
5 2 3 4

6

可能的好的集合 $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$。

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

260

数据范围

• $1 \le N \le 100$
• $S_i$ 是由小写英文字母组成的字符串
• $1 \le |S_i|$
• $|S_1| + |S_2| + \ldots + |S_N| \le 5000$
• $1 \le A_i \le 10^9$