分数: 625 点
问题陈述
你被给予 N 字符串 S_1, S_2, \ldots, S_N 由小写英文字母和 N 正整数 A_1, A_2, \ldots, A_N.
一个子集 T of \lbrace 1, 2, \ldots, N \rbrace 被称为 好套装 如果没有配对 i, j \in T (i \neq j) 这样 S_i 是一个子串 S_j.
找到最大可能值 \displaystyle \sum_{i \in T} A_i 一套好 T.
什么是子串? 字符串的
A 子字符串 一个字符串的 S 是从开头删除零个或多个字符,从结尾删除零个或多个字符得到的字符串 S。 例如,ab 是一个子串 abc,但是 ac 不是以下的子串 abc.
约束
- 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
输入
输入由标准输入按以下格式给出:
N S_1 S_2 \vdots S_N A_1 A_2 \ldots A_N
输出
打印答案。
示例输入 1
4 atcoder at coder code 5 2 3 4
示例输出 1
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.
示例输入 2
10 abcd abc ab a b c d ab bc cd 100 10 50 30 60 90 80 70 40 20
示例输出 2
260