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 ≤ 105) — the number of strings in t.Each of the next n lines contains contains a non-empty string ti. ti 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 ci ( - 107 ≤ ci ≤ 107) — 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<br />aa<br />bb<br />2 1<br />2<br />aa<br />ab<br />2 1<br />
加载中...