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;
string t[maxn];
int cost[maxn];
int pos[maxn];
int COST[maxn];
int maxlen[maxn];
int MAXLEN[maxn];
long long SUMCOST[maxn];
int st[4 * maxn];
void build(int node, int L, int R) {
  if (L == R) {
    st[node] = LCP[L];
    return;
  }
  build(node << 1, L, (L + R) >> 1);
  build((node << 1) + 1, ((L + R) >> 1) + 1, R);
  st[node] = min(st[node << 1], st[(node << 1) + 1]);
}
int query(int node, int l, int r, int L, int R) {
  if (l > R || r < L) return INF;
  if (l <= L && r >= R) return st[node];
  return min(query(node << 1, l, r, L, (L + R) >> 1),
             query((node << 1) + 1, l, r, ((L + R) >> 1) + 1, R));
}
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));
  cin >> n;
  for (int i = (0); i < (n); i++) {
    cin >> t[i];
    for (int j = (0); j < (int((t[i]).size())); j++) {
      pos[nlen] = i;
      maxlen[nlen] = int((t[i]).size()) - j;
      T[nlen++] = t[i][j];
    }
    T[nlen++] = '$';
  }
  for (int i = (0); i < (n); i++) cin >> 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];
  }
  build(1, 0, nlen - 1);
  long long ans = 0;
  for (int i = (1); i < (nlen); i++) {
    if (!LCP[i] && (i == nlen - 1 || !LCP[i + 1])) {
      ans = max(ans, MAXLEN[i] * calc(i, i));
      continue;
    }
    int l = i, r = nlen - 1;
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (query(1, i, mid, 0, nlen - 1) >= LCP[i])
        l = mid;
      else
        r = mid - 1;
    }
    int R = l;
    l = 0, r = i;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (query(1, mid, i, 0, nlen - 1) < LCP[i])
        l = mid + 1;
      else
        r = mid;
    }
    int L = l;
    ans = max(ans, LCP[i] * calc(L - 1, R));
    if (MAXLEN[i] > LCP[i] && (i == nlen - 1 || MAXLEN[i] > LCP[i + 1]))
      ans = max(ans, MAXLEN[i] * calc(i, i));
  }
  cout << ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  solve();
  return 0;
}