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

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