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;
const int maxn = 1e5 + 79, maxlen = 6e5 + 79;
vector<int> s(maxlen, 1), p(maxlen), l(maxlen), r(maxlen), lcp(maxlen, 0);
vector<long long> sum;
int highest(int v) {
  while (v != p[v]) v = p[v];
  return v;
}
long long merge(int a, int b) {
  a = highest(a);
  b = highest(b);
  if (a == b) return sum[a];
  if (s[a] < s[b]) swap(a, b);
  s[a] += s[b];
  sum[a] += sum[b];
  p[b] = a;
  l[a] = min(l[a], l[b]);
  r[a] = max(r[a], r[b]);
  return sum[a];
}
vector<int> suffix_array(vector<int>& s, int abc) {
  int n = s.size();
  vector<int> p(n), c(n, 0), pn(n), cn(n), cnt(abc, 0);
  for (int i : s) cnt[i]++;
  for (int i = 1; i < abc; i++) cnt[i] += cnt[i - 1];
  for (int i = 0; i < n; i++) p[--cnt[s[i]]] = i;
  int cl = 1;
  for (int i = 1; i < n; i++) {
    if (s[p[i]] != s[p[i - 1]]) cl++;
    c[p[i]] = cl - 1;
  }
  for (int h = 0; (1 << h) < n; h++) {
    for (int i = 0; i < n; i++) pn[i] = (n + p[i] - (1 << h)) % n;
    cnt.assign(cl, 0);
    for (int i = 0; i < n; i++) cnt[c[pn[i]]]++;
    for (int i = 1; i < cl; i++) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; i--) p[--cnt[c[pn[i]]]] = pn[i];
    cn[p[0]] = 0;
    cl = 1;
    for (int i = 1; i < n; i++) {
      pair<int, int> nw = {c[p[i]], c[(p[i] + (1 << h)) % n]},
                     pv = {c[p[i - 1]], c[(p[i - 1] + (1 << h)) % n]};
      if (nw != pv) cl++;
      cn[p[i]] = cl - 1;
    }
    c = cn;
  }
  return p;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<vector<int> > t(n);
  vector<int> all, c(n), siz, sum1;
  for (int i = 0; i < n; i++) {
    string tmp;
    cin >> tmp;
    for (int j : tmp) t[i].push_back(n + j - 'a');
  }
  for (int i = 0; i < n; i++) {
    cin >> c[i];
    for (int j = 0; j < t[i].size(); j++) {
      all.push_back(t[i][j]);
      siz.push_back(t[i].size() - j);
      sum1.push_back(c[i]);
    }
    all.push_back(i);
    siz.push_back(0);
    sum1.push_back(0);
  }
  for (int i = 0; i < all.size(); i++) p[i] = l[i] = r[i] = i;
  vector<int> sf = suffix_array(all, n + 26), inv(all.size());
  vector<pair<int, int> > lv;
  for (int i = 0; i < sf.size(); i++) inv[sf[i]] = i;
  sum.resize(sum1.size());
  for (int i = 0; i < sum.size(); i++) sum[inv[i]] = sum1[i];
  long long ans = 0;
  for (int i = 0, k = 0; i < all.size(); i++, k = (k ? k - 1 : 0)) {
    if (inv[i] == sf.size() - 1) {
      k = 0;
      continue;
    }
    int j = sf[inv[i] + 1];
    while (max(j, i) + k < all.size() && all[i + k] == all[j + k]) k++;
    lcp[inv[i]] = k;
    lv.push_back({k, inv[i]});
  }
  sort(lv.begin(), lv.end(), greater<pair<int, int> >());
  for (int i = 0; i < all.size(); i++)
    if (inv[i] && max(lcp[inv[i] - 1], lcp[inv[i]]) < siz[i])
      ans = max(ans, siz[i] * 1ll * sum1[i]);
  for (pair<int, int>& i : lv) {
    long long val = merge(i.second, i.second + 1) * 1ll * i.first;
    int h = highest(i.second);
    if (max((l[h] ? lcp[l[h] - 1] : -1), lcp[r[h]]) < i.first)
      ans = max(ans, val);
  }
  cout << ans << "\n";
  return 0;
}