给你 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