[ABC354] G - Select Strings

G - Select Strings

Time Limit: 2 sec / Memory Limit: 1024 MB

分数：625分

题面

给定 个字符串 ，由小写英文字母组成，以及 个正整数 。

称 的一个子集 为 好子集，如果不存在 中的 使得 是 的子串。

找出满足上述条件的好子集 中 的最大可能值。

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

限制条件

• 是由小写英文字母组成的字符串。

---

输入

输入从标准输入给出，格式如下：

输出

输出答案。

---

输入样例 1

4
atcoder
at
coder
code
5 2 3 4

输出样例 1

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