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;
int wa[600001 + 1001], wb[600001 + 1001], wv[600001 + 1001], Ws[600001 + 1001];
int cmp(int *r, int a, int b, int l) {
  return r[a] == r[b] && r[a + l] == r[b + l];
}
void da(const int r[], int sa[], int n, int m) {
  int i, j, p, *x = wa, *y = wb, *t;
  for (i = 0; i < m; i++) Ws[i] = 0;
  for (i = 0; i < n; i++) Ws[x[i] = r[i]]++;
  for (i = 1; i < m; i++) Ws[i] += Ws[i - 1];
  for (i = n - 1; i >= 0; i--) sa[--Ws[x[i]]] = i;
  for (j = 1, p = 1; p < n; j *= 2, m = p) {
    for (p = 0, i = n - j; i < n; i++) y[p++] = i;
    for (i = 0; i < n; i++)
      if (sa[i] >= j) y[p++] = sa[i] - j;
    for (i = 0; i < n; i++) wv[i] = x[y[i]];
    for (i = 0; i < m; i++) Ws[i] = 0;
    for (i = 0; i < n; i++) Ws[wv[i]]++;
    for (i = 1; i < m; i++) Ws[i] += Ws[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--Ws[wv[i]]] = y[i];
    for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++)
      x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
  }
  return;
}
int sa[600001], Rank[600001], height[600001];
void calheight(const int *r, int *sa, int n) {
  int i, j, k = 0;
  for (i = 1; i <= n; i++) Rank[sa[i]] = i;
  for (i = 0; i < n; height[Rank[i++]] = k)
    for (k ? k-- : 0, j = sa[Rank[i] - 1]; r[i + k] == r[j + k]; k++)
      ;
  for (int i = n; i >= 1; --i) ++sa[i], Rank[i] = Rank[i - 1];
}
char str[600001];
long long ans, sum[600001];
int n, c[600001], s[600001], leng[600001], belong[600001], _l[600001],
    _r[600001], len_sum;
void rua(int L, int R) {
  long long res = 0, x, le;
  for (int i = L; i <= R; i++) {
    x = belong[sa[i] - 1];
    le = leng[x] - sa[i] + 1;
    if ((i == R || height[i + 1] < le) && (i == L || height[i] < le))
      res = max(res, 1ll * le * c[x]);
  }
  for (int i = L; i <= R; i++)
    res = max(res, 1ll * height[i] *
                       (sum[min(R, _r[i])] - sum[max(L, _l[i] - 1) - 1]));
  ans = max(ans, res);
}
int main() {
  scanf("%d", &n);
  scanf("%s", str);
  int len = strlen(str);
  for (int i = 0; i < len; i++)
    belong[len_sum] = 1, s[len_sum++] = str[i] + 600001;
  leng[1] = len_sum;
  for (int i = 2; i <= n; i++) {
    s[len_sum++] = i;
    scanf("%s", str);
    len = strlen(str);
    for (int j = 0; j < len; j++)
      belong[len_sum] = i, s[len_sum++] = str[j] + 600001;
    leng[i] = len_sum;
  }
  da(s, sa, len_sum + 1, 600001 + 1000);
  calheight(s, sa, len_sum);
  for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
  for (int i = 1; i <= len_sum; i++) sum[i] = sum[i - 1] + c[belong[sa[i] - 1]];
  _l[1] = 1, _r[len_sum] = len_sum;
  for (int i = 2; i <= len_sum; i++) {
    int _ = i;
    while (_ > 1 && height[i] <= height[_ - 1]) _ = _l[_ - 1];
    _l[i] = _;
  }
  for (int i = len_sum - 1; i >= 1; i--) {
    int _ = i;
    while (_ < len_sum && height[i] <= height[_ + 1]) _ = _r[_ + 1];
    _r[i] = _;
  }
  for (int l = 1; l <= len_sum; l++)
    if (s[sa[l] - 1] > 600001) {
      int r = l;
      while (r <= len_sum && s[sa[r] - 1] > 600001) r++;
      rua(l, r - 1);
      l = r;
    }
  printf("%I64d\n", ans);
}