CF616F.Expensive Strings

You are given n strings t__i. Each string has cost c__i.

Let's define the function of string , where p__s, i is the number of occurrences of s in t__i, |s| is the length of the string s. Find the maximal value of function f(s) over all strings.

Note that the string s is not necessarily some string from t.

给你 $ n $ 个字符串 $ t_i $，每个字符串 $ t_i $ 有一个代价 $ c_i $。

定义字符串 $ s $ 的函数
，
其中 $ p_{s,i} $ 表示字符串 $ s $ 在 $ t_i $ 中的出现次数，$ |s| $ 表示字符串 $ s $ 的长度。求函数 $ f(s) $ 在所有可能字符串 $ s $ 上的最大值。

注意：字符串 $ s $ 不一定出现在给定的 $ t_i $ 中。

The first line contains the only integer n (1 ≤ n ≤ 105) — the number of strings in t.

Each of the next n lines contains contains a non-empty string t__i. t__i contains only lowercase English letters.

It is guaranteed that the sum of lengths of all strings in t is not greater than 5·105.

The last line contains n integers c__i ( - 107 ≤ c__i ≤ 107) — the cost of the i-th string.

第一行包含唯一一个整数 $n$（$1 \leq n \leq 10^5$）——即字符串集合 $t$ 中字符串的个数。

接下来的 $n$ 行，每行包含一个非空字符串 $t_i$。每个 $t_i$ 仅由小写英文字母组成。

保证 $t$ 中所有字符串的长度之和不超过 $5 \cdot 10^5$。

最后一行包含 $n$ 个整数 $c_i$（$-10^7 \leq c_i \leq 10^7$）——表示第 $i$ 个字符串的代价。

Print the only integer a — the maximal value of the function f(s) over all strings s. Note one more time that the string s is not necessarily from t.

输出唯一的整数 $a$ —— 函数 $f(s)$ 在所有字符串 $s$ 上的最大值。请注意，字符串 $s$ 不一定来自 $t$。