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;
string inp[100005];
int num[100005];
int tl;
int ch[1200005][27];
int fail[1200005], len[1200005], elen[1200005];
long long cost[1200005];
int rt = 1, tot = 1, last = 1;
void add(int x, int c, int _elen) {
  int p = last;
  int np = ++tot;
  len[np] = len[p] + 1;
  cost[np] = c;
  elen[np] = _elen;
  last = np;
  while (p && !ch[p][x]) {
    ch[p][x] = np;
    p = fail[p];
  }
  if (!p) {
    fail[np] = rt;
  } else {
    int q = ch[p][x];
    if (len[q] == len[p] + 1) {
      fail[np] = q;
    } else {
      int nq = ++tot;
      memcpy(ch[nq], ch[q], sizeof(ch[q]));
      len[nq] = len[p] + 1;
      fail[nq] = fail[q];
      fail[np] = fail[q] = nq;
      while (p && ch[p][x] == q) {
        ch[p][x] = nq;
        p = fail[p];
      }
    }
  }
}
int freq[600005], tpsort[1200005];
void TopoSort() {
  for (int i = (1); i <= (tot); i += (1)) freq[len[i]]++;
  for (int i = (1); i <= (tl); i += (1)) freq[i] += freq[i - 1];
  for (int i = (tot); i >= (1); i -= (1)) tpsort[--freq[len[i]]] = i;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = (1); i <= (n); i += (1)) cin >> inp[i];
  for (int i = (1); i <= (n); i += (1)) cin >> num[i];
  for (int i = (0); i <= (1200005 - 1); i += (1)) elen[i] = 1000000000;
  tl = 0;
  for (int i = (1); i <= (n); i += (1)) {
    int t = inp[i].length();
    for (int j = (0); j <= (t - 1); j += (1)) {
      add(inp[i][j] - 'a', num[i], j + 1);
    }
    add(26, 0, 0);
    tl += t + 1;
  }
  TopoSort();
  long long mx = 0;
  for (int i = (tot); i >= (1); i -= (1)) {
    int u = tpsort[i];
    cost[fail[u]] += cost[u];
    elen[fail[u]] = min(elen[fail[u]], elen[u]);
    if (elen[u] > len[fail[u]]) {
      mx = max(mx, cost[u] * min(elen[u], len[u]));
    }
  }
  printf("%lld\n", mx);
  return 0;
}