← 返回题目列表

Codeforces · 616/F

F. 昂贵的琴弦

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

给你 n 个字符串 ti。每个字符串都有成本 ci。

让我们定义字符串 $$s 的函数: f(s) = \sum_{i=1}^{n} c_i \cdot p_{s,i} \cdot |s|$$,其中 ps, i 是 s 在 ti, |s| 中出现的次数。是字符串 s 的长度。求函数 f(s) 在所有字符串上的最大值。

请注意,字符串 s 不一定是 t 中的某个字符串。

输入

第一行包含唯一的整数 n (1 ≤ n ≤ 105) — t 中的字符串数量。

接下来的 n 行中的每一行都包含一个非空字符串 ti。 ti 仅包含小写英文字母。

保证t中所有字符串的长度之和不大于5·105。

最后一行包含 n 个整数 ci ( - 107 ≤ ci ≤ 107) — 第 i 个字符串的成本。

输出

打印唯一的整数 a — 函数 f(s) 在所有字符串 s 上的最大值。请再次注意,字符串 s 不一定来自 t。

示例

输入 #1

2
aa
bb
2 1

输出 #1

4

输入 #2

2
aa
ab
2 1

输出 #2

5