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 tmp1[600001 + 1001], tmp2[600001 + 1001], tmp3[600001 + 1001],
    tmp4[600001 + 1001];
int *wa = tmp1 + 500, *wb = tmp2 + 500, *wv = tmp3 + 500, *Ws = tmp4 + 500;
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, a[600001], sum[600001], L, R, M, S;
struct rua {
  long long l, r, w, s, lw, rw;
} t[600001 << 2];
int n, c[600001], s[600001], leng[600001], belong[600001], _l[600001],
    _r[600001], len_sum;
void ShowInfo(int len) {
  puts("--------------All Suffix--------------");
  for (int i = 1; i <= len; ++i) {
    printf("%d:\t", i);
    for (int j = i - 1; j < len; ++j)
      if (s[j] < 600001)
        printf("%d", s[j]);
      else
        printf("%c", s[j] - 600001);
    puts("");
  }
  puts("");
  puts("-------------After sort---------------");
  for (int i = 1; i <= len; ++i) {
    printf("sa[%2d ] = %2d\t", i, sa[i]);
    for (int j = sa[i] - 1; j < len; ++j)
      if (s[j] < 600001)
        printf("%d", s[j]);
      else
        printf("%c", s[j] - 600001);
    puts("");
  }
  puts("");
  puts("---------------Height-----------------");
  for (int i = 1; i <= len; ++i) printf("height[%2d ]=%2d \n", i, height[i]);
  puts("");
  puts("----------------Rank------------------");
  for (int i = 1; i <= len; ++i) printf("Rank[%2d ] = %2d\n", i, Rank[i]);
  puts("------------------END-----------------");
}
void up(int x, int mid) {
  t[x].s = t[x * 2].s + t[x * 2 + 1].s;
  t[x].w = max(t[x * 2].w, t[x * 2 + 1].w);
  t[x].lw = max(t[x * 2].lw, t[x * 2].s + t[x * 2 + 1].lw);
  t[x].rw = max(t[x * 2 + 1].rw, t[x * 2 + 1].s + t[x * 2].rw);
  t[x].w = max(t[x].w, t[x * 2].rw + t[x * 2 + 1].lw);
}
void Build(int l, int r, int x) {
  t[x].l = l, t[x].r = r;
  if (l == r) {
    t[x].w = t[x].lw = t[x].rw = t[x].s = a[l];
    return;
  }
  int mid = l + r >> 1;
  Build(l, mid, x * 2);
  Build(mid + 1, r, x * 2 + 1);
  up(x, mid);
}
void ask(int ll, int rr, int l, int r, int x) {
  if (ll > r || l > rr) return;
  int mid = l + r >> 1;
  if (ll <= l && r <= rr) {
    M = max(M, max(t[x].w, R + t[x].lw));
    L = max(L, S + t[x].w);
    R = max(R + t[x].s, t[x].rw);
    M = max(M, max(L, R));
    S += t[x].s;
    return;
  }
  ask(ll, rr, l, mid, x * 2);
  ask(ll, rr, mid + 1, r, x * 2 + 1);
}
void rua(int lL, int rR) {
  long long res = 0, x, le;
  for (int i = lL; i <= rR; i++) {
    x = belong[sa[i] - 1];
    le = leng[x] - sa[i] + 1;
    if ((i == rR || height[i + 1] < le) && (i == lL || height[i] < le))
      res = max(res, 1ll * le * c[x]);
  }
  for (int i = lL; i <= rR; i++) {
    res = max(res, 1ll * height[i] *
                       (sum[min(rR, _r[i])] - sum[max(lL, _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++)
    a[i] = c[belong[sa[i] - 1]], sum[i] = a[i] + sum[i - 1];
  Build(1, len_sum, 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);
}