#P13505. [ABC354G] Select Strings

    ID: 12688 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-KMP消除被支配候选二分图建模最小割建模Dinic最大流最小割定理

[ABC354G] Select Strings

AT_abc354_g [ABC354G] Select Strings

题目描述

有 NN 个仅由小写英文字母组成的字符串 S1,S2,…,SNS_1,S_2,\ldots,S_N,以及 NN 个正整数 A1,A2,…,ANA_1,A_2,\ldots,A_N。

对于集合 {1,2,…,N}\lbrace 1,2,\ldots,N \rbrace 的某个子集 TT,如果对于任意 i,j∈Ti,j \in T 且 i≠ji \neq j,都不存在 SiS_i 是 SjS_j 的子串的情况,则称 TT 为好集合。

请你选择一个好集合 TT,使得 ∑i∈TAi\displaystyle\sum_{i\in T}A_i 的值最大,并输出这个最大值。

子串的定义:字符串 SS 的子串是指通过从 SS 的开头删除 00 个或多个字符、从结尾删除 00 个或多个字符后得到的字符串。例如,ab 是 abc 的子串,但 ac 不是 abc 的子串。

输入格式

输入按以下格式从标准输入读入。

NN
S1S_1
S2S_2
⋮\vdots
SNS_N
A1 A2 … ANA_1\ A_2\ \ldots\ A_N

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4
atcoder
at
coder
code
5 2 3 4

输出 #1

6

输入输出样例 #2

输入 #2

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

输出 #2

260

说明/提示

限制条件

  • 1≤N≤1001 \leq N \leq 100
  • SiS_i 由小写英文字母组成
  • 1≤∣Si∣1 \leq |S_i|
  • ∣S1∣+∣S2∣+…+∣SN∣≤5000|S_1|+|S_2|+\ldots+|S_N| \leq 5000
  • 1≤Ai≤1091 \leq A_i \leq 10^9

样例解释 1

作为好集合的 TT 及其对应的 ∑i∈TAi\displaystyle\sum_{i\in T}A_i 如下:

  • 当 T={1}T = \lbrace 1 \rbrace 时,∑i∈TAi=5\displaystyle\sum_{i\in T}A_i = 5
  • 当 T={2}T = \lbrace 2 \rbrace 时,∑i∈TAi=2\displaystyle\sum_{i\in T}A_i = 2
  • 当 T={3}T = \lbrace 3 \rbrace 时,∑i∈TAi=3\displaystyle\sum_{i\in T}A_i = 3
  • 当 T={4}T = \lbrace 4 \rbrace 时,∑i∈TAi=4\displaystyle\sum_{i\in T}A_i = 4
  • 当 T={2,3}T = \lbrace 2,3 \rbrace 时,∑i∈TAi=5\displaystyle\sum_{i\in T}A_i = 5
  • 当 T={2,4}T = \lbrace 2,4 \rbrace 时,∑i∈TAi=6\displaystyle\sum_{i\in T}A_i = 6

其中最大值为 66,因此输出 66。