Expensive Strings

题意翻译

给你$n$个字符串。每个字符串的成本都是$c_i$。 定义字符串的函数，其中$f(s)=\sum_{i=1}^n c_i \cdot p_{s,i} \cdot |s|$，$p_{s,i}$是$s$在$t_i$中出现的次数，$|s|$是字符串$s$的长度。求**所有字符串函数$f(s)$的最大值**。 注意字符串$s$**不一定**是$t$中的某个字符串。

题目描述

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 $ .

输入输出格式

输入格式

The first line contains the only integer $ n $ ( $ 1<=n<=10^{5} $ ) — 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·10^{5} $ . The last line contains $ n $ integers $ c_{i} $ ( $ -10^{7}<=c_{i}<=10^{7} $ ) — the cost of the $ i $ -th string.

输出格式

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 $ .

输入输出样例

输入样例 #1

2
aa
bb
2 1

输出样例 #1

4

输入样例 #2

2
aa
ab
2 1

输出样例 #2

5