题目背景

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

题目描述

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

Banana 定义两个祝福 \(X\) 和 \(Y\) 相似，当且仅当他们满足下面条件中的至少一个：

• \(X\) 是 \(Y\) 的子串。
• \(Y\) 是 \(X\) 的子串。
• 存在另一个祝福 \(Z\)，使得 \(X\) 和 \(Z\) 相似且 \(Y\) 和 \(Z\) 相似。

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

另外，每个祝福都有一个祝福值，其中第 \(i\) 个祝福的祝福值为 \(a_i\)。

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

输入格式

第一行一个整数表示 \(n\)。

第二行 \(n\) 个整数 \(a_i\)。

接下来 \(n\) 行，第 \(i\) 行一个字符串 \(S_i\) 表示一个祝福。

输出格式

一行一个整数表示答案。

样例

输入样例 #1

5
1 2 3 4 5
aa
aaa
aaaa
bbb
bbbb

输出样例 #1

8

数据范围

\(1\leq n\leq 3\times 10^4\)，\(1\leq \sum |S_i|\leq 10^5\)，\(1\leq a_i\leq 10^9\)