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;
long long gcd(long long a, long long b) {
  long long r;
  while (b != 0) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long fpow(long long n, long long k, int p = (int)1e9 + 7) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
const int MOD = (int)1e9 + 7;
const int INF = (int)1e9;
const long long LINF = (long long)1e18;
const long double PI = 2 * acos((long double)0);
const int MAXN = 600010;
char T[MAXN];
int nlen;
int RA[MAXN], tempRA[MAXN];
int SA[MAXN], tempSA[MAXN];
int c[MAXN];
int Phi[MAXN], PLCP[MAXN];
int LCP[MAXN];
void countingsort(int k) {
  int sum = 0, maxi = max(300, nlen);
  memset(c, 0, sizeof(c));
  for (int i = 0; i < nlen; i++) c[i + k < nlen ? RA[i + k] : 0]++;
  for (int i = 0; i < maxi; i++) {
    int t = c[i];
    c[i] = sum;
    sum += t;
  }
  for (int i = 0; i < nlen; i++)
    tempSA[c[SA[i] + k < nlen ? RA[SA[i] + k] : 0]++] = SA[i];
  for (int i = 0; i < nlen; i++) SA[i] = tempSA[i];
}
void constructSA() {
  int r;
  for (int i = 0; i < nlen; i++) RA[i] = T[i];
  for (int i = 0; i < nlen; i++) SA[i] = i;
  for (int k = 1; k < nlen; k <<= 1) {
    countingsort(k);
    countingsort(0);
    tempSA[SA[0]] = r = 0;
    for (int i = 1; i < nlen; i++)
      tempRA[SA[i]] =
          (RA[SA[i]] == RA[SA[i - 1]] && RA[SA[i] + k] == RA[SA[i - 1] + k])
              ? r
              : ++r;
    for (int i = 0; i < nlen; i++) RA[i] = tempRA[i];
    if (RA[SA[nlen - 1]] == nlen - 1) break;
  }
}
void computeLCP() {
  int L = 0;
  Phi[SA[0]] = -1;
  for (int i = 1; i < nlen; i++) Phi[SA[i]] = SA[i - 1];
  for (int i = 0; i < nlen; i++) {
    if (Phi[i] == -1) {
      PLCP[i] = 0;
      continue;
    }
    while (T[i + L] == T[Phi[i] + L] && T[i + L] != '$') L++;
    PLCP[i] = L;
    L = max(L - 1, 0);
  }
  for (int i = 0; i < nlen; i++) LCP[i] = PLCP[SA[i]];
}
const int maxn = 600010;
int n;
char s[maxn];
int cost[maxn];
int pos[maxn];
int COST[maxn];
int maxlen[maxn];
int MAXLEN[maxn];
long long SUMCOST[maxn];
int l[maxn];
int r[maxn];
long long calc(int l, int r) {
  if (!l) return SUMCOST[r];
  return SUMCOST[r] - SUMCOST[l - 1];
}
void solve() {
  memset(pos, -1, sizeof(pos));
  scanf("%d", &n);
  for (int i = (0); i < (n); i++) {
    scanf("%s", s);
    int d = strlen(s);
    for (int j = (0); j < (d); j++) {
      pos[nlen] = i;
      maxlen[nlen] = d - j;
      T[nlen++] = s[j];
    }
    T[nlen++] = '$';
  }
  for (int i = (0); i < (n); i++) scanf("%d", cost + i);
  constructSA();
  computeLCP();
  for (int i = (0); i < (nlen); i++) {
    if (~pos[i]) {
      COST[RA[i]] = cost[pos[i]];
      MAXLEN[RA[i]] = maxlen[i];
    }
  }
  for (int i = (0); i < (nlen); i++) {
    if (!i)
      SUMCOST[i] = COST[i];
    else
      SUMCOST[i] = SUMCOST[i - 1] + COST[i];
  }
  for (int i = (0); i < (nlen); i++) l[i] = r[i] = i;
  for (int i = (1); i < (nlen); i++) {
    int cur = i;
    while (cur && LCP[i] <= LCP[cur - 1]) cur = l[cur - 1];
    l[i] = cur;
  }
  for (int i = (nlen - 1) - 1; i >= (0); i--) {
    int cur = i;
    while (cur < nlen - 1 && LCP[i] <= LCP[cur + 1]) cur = r[cur + 1];
    r[i] = cur;
  }
  long long ans = 0;
  for (int i = (1); i < (nlen); i++) {
    ans = max(ans, LCP[i] * calc(l[i] - 1, r[i]));
    if (MAXLEN[i] > LCP[i] && (i == nlen - 1 || MAXLEN[i] > LCP[i + 1]))
      ans = max(ans, MAXLEN[i] * calc(i, i));
  }
  printf("%I64d", ans);
}
int main() {
  solve();
  return 0;
}