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;
long long int c[600005];
string str;
int str_ind[600005], str_end[600005];
int n;
void input() {
  scanf("%d", &n);
  cin >> str;
  for (int j = 0; j < str.size(); j++) {
    str_ind[j] = 0;
    str_end[j] = str.size() - 1;
  }
  for (int i = 1; i < n; i++) {
    string t;
    cin >> t;
    str_ind[str.size()] = str_end[str.size()] = -1;
    for (int j = str.size() + 1; j < str.size() + 1 + t.size(); j++) {
      str_ind[j] = i;
      str_end[j] = str.size() + t.size();
    }
    str += "#" + t;
  }
  for (int i = 0; i < n; i++) scanf("%lld", &c[i]);
}
vector<pair<pair<int, int>, int> > suf;
void create_suf() {
  for (int i = 0; i < str.size(); i++)
    suf.push_back(make_pair(
        make_pair(str[i], (i + 1 < str.size()) ? str[i + 1] : -1), i));
  int mul = 1;
  while (mul < str.size()) {
    mul *= 2;
    sort(suf.begin(), suf.end());
    for (int i = 0, rank = 1; i < suf.size() - 1; i++) {
      int oldrank = rank;
      if (suf[i].first.first != suf[i + 1].first.first ||
          suf[i].first.second != suf[i + 1].first.second)
        rank++;
      suf[i].first.first = oldrank;
      if (i == suf.size() - 2) suf[i + 1].first.first = rank;
    }
    int rank[600005];
    for (int i = 0; i < suf.size(); i++)
      rank[suf[i].second] = suf[i].first.first;
    for (int i = 0; i < suf.size(); i++) {
      int tem = suf[i].second + mul;
      suf[i].first.second = (tem < str.size()) ? rank[tem] : -1;
    }
  }
}
int lcp[600005] = {0}, ord[600005];
void create_lcp() {
  for (int i = 0; i < str.size(); i++) ord[suf[i].second] = i;
  int j = 0, len = str.size();
  for (int i = 0; i < len; i++) {
    if (ord[i] == 0) continue;
    while (i + j < len and suf[ord[i] - 1].second + j < len and
           str[i + j] == str[suf[ord[i] - 1].second + j] and str[i + j] != '#')
      j++;
    lcp[ord[i]] = j;
    if (j) j--;
  }
}
vector<int> invlcp[600005];
int dsu[600005], left1[600005], right1[600005], size[600005];
int parent(int x) {
  if (dsu[x] == x) return x;
  return parent(dsu[x]);
}
void merge(int x, int y) {
  x = parent(x);
  y = parent(y);
  assert(x != y);
  if (x == y) return;
  if (size[x] < size[y]) swap(x, y);
  dsu[y] = x;
  size[x] += size[y];
  left1[x] = min(left1[x], left1[y]);
  right1[x] = max(right1[x], right1[y]);
}
long long int cum[600005];
long long int calcum(int l, int r) {
  long long int ret = cum[r];
  if (l > 0) ret -= cum[l - 1];
  return ret;
}
int main() {
  input();
  create_suf();
  create_lcp();
  for (int i = 0; i < 600005; i++) {
    dsu[i] = left1[i] = right1[i] = i;
    size[i] = 1;
  }
  for (int i = 1; i < str.size(); i++) invlcp[lcp[i]].push_back(i);
  for (int i = 0; i < suf.size(); i++) {
    int tem = str_ind[suf[i].second];
    cum[i] = ((i > 0) ? cum[i - 1] : 0) + ((tem != -1) ? c[tem] : 0);
  }
  long long int ans = 0;
  for (int i = 600005 - 1; i >= 1; i--) {
    for (int j = 0; j < invlcp[i].size(); j++) {
      int ind = invlcp[i][j];
      merge(ind - 1, ind);
      int p = parent(ind);
      if (lcp[left1[p]] < i && lcp[right1[p] + 1] < i)
        ans = max(ans, i * calcum(left1[p], right1[p]));
    }
  }
  for (int i = 0; i < suf.size(); i++) {
    int end = str_end[suf[i].second];
    if (end == -1) continue;
    int tem = max(lcp[i], lcp[i + 1]);
    if (tem < end - suf[i].second + 1)
      ans = max(ans, (end - suf[i].second + 1) * c[str_ind[suf[i].second]]);
  }
  printf("%lld\n", ans);
  return 0;
}