Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Expensive Strings

time limit per test

6 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou 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*.

Input

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.

Output

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

Examples

Input

2

aa

bb

2 1

Output

4

Input

2

aa

ab

2 1

Output

5

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/31/2020 01:11:14 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|