← 返回题目列表

AtCoder · abc354_g

G. 选择字符串

中文机器翻译题面 查看原题

分数: 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