上面挂满我的所有祝福

上面挂满我的所有祝福

题目背景

在巴黎奥运会上,中国代表团取得了 4040 金 的好成绩,于是 Banana 给所有中国运动员送出了祝福。

题目描述

Banana 的祝福可以看作一个由小写字母组成的字符串。现在,Banana 要从他的 nn 个祝福里选若干个送出。

Banana 定义两个祝福 XXYY 相似,当且仅当他们满足下面条件中的至少一个:

  • XXYY 的子串。
  • YYXX 的子串。
  • 存在另一个祝福 ZZ,使得 XXZZ 相似且 YYZZ 相似。

为了使祝福的效果最大化,Banana 不能同时送出两个相似的祝福。

另外,每个祝福都有一个祝福值,其中第 ii 个祝福的祝福值为 aia_i

现在 Banana 想知道他能送出的最大祝福值是多少。

输入格式

第一行一个整数表示 nn

第二行 nn 个整数 aia_i

接下来 nn 行,第 ii 行一个字符串 SiS_i 表示一个祝福。

输出格式

一行一个整数表示答案。

样例

输入样例 #1

5
1 2 3 4 5
aa
aaa
aaaa
bbb
bbbb

输出样例 #1

数据范围

1n3×1041\leq n\leq 3\times 10^41Si1051\leq \sum |S_i|\leq 10^51ai1091\leq a_i\leq 10^9

信息

ID
1004
难度
5
分类
(无)
标签
递交数
6
已通过
1
通过率
17%
上传者