Problem: You are given n strings ti. Each string has cost ci.

Let's define the function of string <image>, where ps, i is the number of occurrences of s in ti, |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 ≤ 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.

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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool upmin(T &x, T y) {
  return y < x ? x = y, 1 : 0;
}
template <typename T>
inline bool upmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
const long double eps = 1e-11;
const long double pi = acos(-1);
const long long oo = 1 << 30;
const long long loo = 1ll << 62;
const long long mods = 998244353;
const long long MAXN = 1000005;
const long long INF = 0x3f3f3f3f;
inline long long read() {
  long long f = 1, x = 0;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 3) + (x << 1) + (c ^ 48);
    c = getchar();
  }
  return x * f;
}
char st[MAXN], s[MAXN];
long long t[MAXN][26], len[MAXN], fa[MAXN], sz = 2, lst = 1, n, fst[MAXN];
long long f[MAXN];
void init() {
  memset(t, 0, (sz + 10) * sizeof t[0]);
  sz = 2, lst = 1;
}
void insert(long long c) {
  long long p = lst, np = lst = sz++;
  len[np] = len[p] + 1;
  for (; p && !t[p][c]; p = fa[p]) t[p][c] = np;
  if (!p) {
    fa[np] = 1;
    return;
  }
  long long q = t[p][c];
  if (len[p] + 1 == len[q])
    fa[np] = q;
  else {
    long long nq = sz++;
    fa[nq] = fa[q];
    fa[np] = fa[q] = nq;
    len[nq] = len[p] + 1;
    memcpy(t[nq], t[q], sizeof t[0]);
    for (; p && t[p][c] == q; p = fa[p]) t[p][c] = nq;
  }
}
long long c[MAXN] = {1}, a[MAXN];
void solve() {
  for (long long i = 1; i <= n; i++) {
    long long nw = 1, x = read();
    for (long long j = fst[i]; j < fst[i + 1]; j++)
      nw = t[nw][st[j] - 'a'], f[nw] += x;
  }
  for (long long i = 1; i < sz; i++) c[i] = 0;
  for (long long i = 1; i < sz; i++) c[len[i]]++;
  for (long long i = 1; i < sz; i++) c[i] += c[i - 1];
  for (long long i = sz - 1; i >= 1; i--) a[--c[len[i]]] = i;
  for (long long i = sz - 1; i >= 1; i--) f[fa[a[i]]] += f[a[i]];
  long long ans = 0;
  for (long long i = 1; i < sz; i++) upmax(ans, f[i] * len[i]);
  printf("%lld\n", ans);
}
signed main() {
  n = read();
  for (long long i = 1; i <= n; i++) {
    lst = 1;
    scanf("%s", s);
    long long len = strlen(s);
    for (long long j = 0; j < len; j++) insert(s[j] - 'a');
    fst[i] += fst[i - 1], fst[i + 1] += len;
    for (long long j = fst[i]; j <= fst[i] + len - 1; j++)
      st[j] = s[j - fst[i]];
  }
  fst[n + 1] += fst[n];
  solve();
  return 0;
}