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;
struct node {
  int ch[26];
  int par, val;
  long long w;
  node(int val = 0) : par(0), val(val) {
    memset(ch, 0, sizeof(ch));
    w = 0;
  }
};
node sam[1000005];
char st[500005];
int val[100005];
int ed[100005];
int b[1000005];
int h[500005];
int n, m, c, last;
void append(int w) {
  int p = last, np, q, nq;
  sam[last = np = ++m] = node(sam[p].val + 1);
  while (p && sam[p].ch[w] == 0) {
    sam[p].ch[w] = np;
    p = sam[p].par;
  }
  if (p == 0) {
    sam[np].par = 1;
    return;
  }
  q = sam[p].ch[w];
  if (sam[p].val + 1 == sam[q].val)
    sam[np].par = q;
  else {
    sam[nq = ++m] = sam[q];
    sam[nq].val = sam[p].val + 1;
    sam[q].par = sam[np].par = nq;
    while (p && sam[p].ch[w] == q) {
      sam[p].ch[w] = nq;
      p = sam[p].par;
    }
  }
}
void init_sam() {
  int i, j, k;
  sam[last = m = 1] = node(0);
  for (i = 1; i <= c; ++i) {
    for (j = ed[i - 1] + 1; j <= ed[i]; ++j) append(st[j] - 'a');
    last = 1;
  }
  for (i = 1; i <= c; ++i)
    for (j = ed[i - 1] + 1, k = sam[1].ch[st[j] - 'a']; j <= ed[i];
         ++j, k = sam[k].ch[st[j] - 'a'])
      sam[k].w += val[i];
}
long long work() {
  long long ans = 0;
  int i;
  for (i = 1; i <= m; ++i) ++h[sam[i].val];
  for (i = 1; i <= n; ++i) h[i] += h[i - 1];
  for (i = m; i > 0; --i) b[h[sam[i].val]--] = i;
  for (i = m; i > 0; --i) sam[sam[b[i]].par].w += sam[b[i]].w;
  for (i = 1; i <= m; ++i) ans = max(ans, sam[i].w * sam[i].val);
  return ans;
}
int main() {
  char cst[500005];
  int i;
  scanf("%d", &c);
  for (i = 1; i <= c; ++i) {
    scanf("%s", cst + 1);
    ed[i] = ed[i - 1] + strlen(cst + 1);
    copy(cst + 1, cst + ed[i] - ed[i - 1] + 1, st + ed[i - 1] + 1);
  }
  n = ed[c];
  for (i = 1; i <= c; ++i) scanf("%d", &val[i]);
  init_sam();
  printf("%I64d\n", work());
  fclose(stdin);
  fclose(stdout);
  return 0;
}