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;
const long long mod = 1000000007;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
const int inf = 0x20202020;
const int N = 1000005;
int n, m;
int r[N], c[N], wb[N + 100], tsa[N + 100], sa[N], b[N], rk[N], lcp[N], slen[N];
long long sum[N];
int bel[N];
bool strhead[N];
long long ans;
bool cmp(int *r, int i, int j, int l) {
  return (r[i] == r[j] && r[i + l] == r[j + l]);
}
void da(int *t) {
  int *x = wb, *y = tsa;
  for (int i = 0; i <= m; i++) b[i] = 0;
  for (int i = 1; i <= n; i++) b[x[i] = t[i]]++;
  for (int i = 1; i <= m; i++) b[i] += b[i - 1];
  for (int i = 1; i <= n; i++) sa[b[x[i]]--] = i;
  for (int j = 1, p = 1; p < n; j *= 2, m = p) {
    p = j;
    for (int i = 1; i <= j; i++) y[i] = n - i + 1;
    for (int i = 1; i <= n; i++)
      if (sa[i] > j) y[++p] = sa[i] - j;
    for (int i = 0; i <= m; i++) b[i] = 0;
    for (int i = 1; i <= n; i++) b[x[i]]++;
    for (int i = 1; i <= m; i++) b[i] += b[i - 1];
    for (int i = n; i >= 1; i--) sa[b[x[y[i]]]--] = y[i];
    t = x;
    x = y;
    y = t;
    x[sa[1]] = 1;
    p = 1;
    for (int i = 2; i <= n; i++)
      x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p : (++p);
  }
  for (int i = 1; i <= n; i++) rk[i] = x[i];
}
void calclcp(int *r) {
  int k = 0, j;
  for (int i = 1; i <= n; i++) {
    j = sa[rk[i] - 1];
    if (j == 0) continue;
    for (k ? k-- : 0; r[j + k] == r[i + k]; k++)
      ;
    lcp[rk[i]] = k;
  }
  lcp[1] = 0;
}
void workon(int le, int ri, int len) {
  le--;
  ans = max(ans, (long long)len * (sum[ri] - sum[le - 1]));
}
stack<pair<int, int> > st;
void lcpinterval() {
  int le;
  pair<int, int> tmp;
  st.push(make_pair(0, 0));
  for (int i = 2; i <= n; i++) {
    le = i;
    while (lcp[i] < st.top().second) {
      tmp = st.top();
      st.pop();
      workon(tmp.first, i - 1, tmp.second);
      le = tmp.first;
    }
    if (lcp[i] > st.top().second) {
      tmp.first = le;
      tmp.second = lcp[i];
      st.push(tmp);
    }
  }
  while (st.top().second != 0) {
    tmp = st.top();
    st.pop();
    workon(tmp.first, n, tmp.second);
  }
}
int main() {
  memset(slen, 0, sizeof(slen));
  memset(strhead, 0, sizeof(strhead));
  int num;
  scanf("%d", &num);
  n = 0;
  char ch;
  for (int i = 1; i <= num; i++) {
    while (scanf("%c", &ch), ch == '\n' || ch == '\r' || ch == ' ')
      ;
    strhead[n + 1] = true;
    while (1) {
      slen[i]++;
      r[++n] = ch - 'a' + 1;
      bel[n] = i;
      scanf("%c", &ch);
      if (ch == '\n' || ch == '\r' || ch == ' ') break;
    }
    r[++n] = 26 + i;
    bel[n] = i;
  }
  for (int i = 1; i <= num; i++) scanf("%d", &c[i]);
  m = 26 + num;
  da(r);
  calclcp(r);
  ans = 0;
  memset(sum, 0, sizeof(sum));
  for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + c[bel[sa[i]]];
  lcpinterval();
  lcp[n + 1] = 0;
  for (int i = 1; i <= n; i++) {
    if (r[sa[i]] > 26) break;
    if (!strhead[sa[i]]) continue;
    int tmplen = slen[bel[sa[i]]];
    if (lcp[i] < tmplen && lcp[i + 1] < tmplen) {
      ans = max(ans, (long long)tmplen * (long long)c[bel[sa[i]]]);
    }
  }
  cout << ans;
  return 0;
}