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>
const int inf = (1ll << 31) - 1;
const int maxn = (int)1e5 + 10;
using namespace std;
int n;
int nsuff[600200];
int suff[600200];
int ncolor[600200];
int color[600200];
int head[600200];
int p[600200];
int lcp[600200];
int second[600100];
int nxt[600100];
int id[600100];
bool cmp(int i, int j) { return second[i] < second[j]; }
int sz = 0;
void suffix_array() {
  int n = sz;
  for (int i = 0; i < n; i++) {
    suff[i] = i;
  }
  sort(suff, suff + n, cmp);
  int cn = 0;
  for (int i = 0; i < n; i++) {
    if (i == 0 || second[suff[i]] != second[suff[i - 1]]) {
      head[cn] = i;
      color[suff[i]] = cn++;
    } else
      color[suff[i]] = cn - 1;
  }
  for (int len = 1; len <= n; len <<= 1) {
    for (int i = 0; i < n; i++) {
      int pos = suff[i] - len;
      if (pos < 0) pos += n;
      ncolor[i] = color[i];
      nsuff[head[color[pos]]++] = pos;
    }
    cn = 0;
    for (int i = 0; i < n; i++) {
      suff[i] = nsuff[i];
      if (i == 0 || ncolor[suff[i]] != ncolor[suff[i - 1]] ||
          ncolor[(suff[i] + len) % n] != ncolor[(suff[i - 1] + len) % n]) {
        head[cn] = i;
        color[suff[i]] = cn++;
      } else
        color[suff[i]] = cn - 1;
    }
  }
  for (int i = 0; i < n; i++) {
    p[suff[i]] = i;
  }
  int m = 0;
  for (int i = 0; i < n; i++) {
    int pos = p[i];
    if (pos == n - 1) {
      lcp[pos] = 0;
      m = 0;
      continue;
    }
    m = max(0, m - 1);
    while (i + m < n && suff[pos + 1] + m < n &&
           second[i + m] == second[suff[pos + 1] + m])
      m++;
    lcp[pos] = m;
  }
}
struct node {
  vector<node *> childrens;
  node *parent;
  int depth;
  long long ans;
  node() {
    parent = NULL;
    depth = 0;
    ans = 0;
  }
  node(node *_parent, int _depth) {
    parent = _parent;
    depth = _depth;
    ans = 0;
  }
};
node *buildsuffixtree(node *&root, int len, int lcp, long long val) {
  if (root->depth == 0 || root->depth == lcp) {
    if (root->depth == len) {
      root->ans += val;
      return root;
    }
    node *added = new node(root, len);
    added->ans += val;
    root->childrens.push_back(added);
    return added;
  }
  if (root->parent->depth < lcp) {
    node *added = new node(root->parent, lcp);
    root->parent->childrens.pop_back();
    root->parent->childrens.push_back(added);
    added->childrens.push_back(root);
    root->parent = added;
  }
  return buildsuffixtree(root->parent, len, lcp, val);
}
int v[200200];
long long ans = 0;
char c[500500];
void traverse(node *&root) {
  for (int i = 0; i < root->childrens.size(); i++) {
    traverse(root->childrens[i]);
    root->ans += root->childrens[i]->ans;
  }
  ans = max(ans, root->ans * 1ll * root->depth);
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%s", &c);
    int m = strlen(c);
    int el = sz + m;
    for (int j = 0; j < m; j++) {
      nxt[sz] = el;
      id[sz] = i;
      second[sz++] = c[j] - 'a';
    }
    nxt[sz] = el;
    id[sz] = i;
    second[sz++] = -1 - i;
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &v[i]);
  }
  suffix_array();
  node *root = new node();
  for (int i = 0; i < sz; i++) {
    if (nxt[suff[i]] == suff[i]) continue;
    root = buildsuffixtree(root, nxt[suff[i]] - suff[i], lcp[i - 1],
                           v[id[suff[i]]]);
  }
  while (root->depth > 0) root = root->parent;
  traverse(root);
  cout << ans << endl;
  return 0;
}