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;
template <class T>
void rd(T &ret) {
  ret = 0;
  bool ok = 0, u = 0;
  for (;;) {
    int c = getchar();
    if (c >= '0' && c <= '9')
      ret = (ret << 3) + (ret << 1) + c - '0', ok = 1;
    else if (c == '-')
      u = 1;
    else if (ok) {
      if (u) ret *= -1;
      return;
    }
  }
}
long long pow_mod(long long p, long long n, long long mod) {
  long long ret = 1;
  for (; n; n >>= 1) {
    if (n & 1) ret = ret * p % mod;
    p = p * p % mod;
  }
  return ret;
}
template <class T>
bool chmin(T &a, const T &b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool chmax(T &a, const T &b) {
  return b > a ? a = b, 1 : 0;
}
const int Max_N = (int)6e5 + 9;
struct DS {
  set<pair<long long, pair<int, int> > > has;
  void init() { has.clear(); }
  void erase(long long c, int l, int r) {
    has.erase(pair<long long, pair<int, int> >(-c, pair<int, int>(l, r)));
  }
  void insert(long long c, int l, int r) {
    has.insert(pair<long long, pair<int, int> >(-c, pair<int, int>(l, r)));
  }
  long long get_max() {
    if (has.empty()) return 0;
    return -(has.begin()->first);
  }
} ds;
struct RMQ {
  int mx[Max_N][30], lg2[Max_N];
  void init(int n, int *a) {
    for (int i = 0; i < n; ++i) {
      mx[i][0] = a[i];
      lg2[i] = (!i ? -1 : lg2[i >> 1] + 1);
    }
    lg2[n] = lg2[n >> 1] + 1;
    for (int j = 1, l = 2; l <= n; ++j, l <<= 1) {
      for (int i = 0; i + l - 1 < n; ++i)
        mx[i][j] = std::min(mx[i][j - 1], mx[i + (l >> 1)][j - 1]);
    }
  }
  int query(int a, int b) {
    int k = lg2[b - a + 1];
    return std::min(mx[a][k], mx[b - (1 << k) + 1][k]);
  }
};
struct SA {
  int n;
  int sa[Max_N];
  int rank[Max_N];
  int h[Max_N];
  int wa[Max_N], wb[Max_N], wv[Max_N], wt[Max_N];
  RMQ rmq;
  int cmp(int *r, int a, int b, int l) {
    return r[a] == r[b] && r[a + l] == r[b + l];
  }
  void init(int *r, int n, int m) {
    r[n] = 0;
    this->n = n++;
    int i, j, p, *first = wa, *second = wb, *t;
    for (i = 0; i < m; ++i) wt[i] = 0;
    for (i = 0; i < n; ++i) wt[first[i] = r[i]]++;
    for (i = 1; i < m; ++i) wt[i] += wt[i - 1];
    for (i = n - 1; i >= 0; --i) sa[--wt[first[i]]] = i;
    for (j = 1, p = 1; p < n; j *= 2, m = p) {
      for (p = 0, i = n - j; i < n; i++) second[p++] = i;
      for (i = 0; i < n; ++i)
        if (sa[i] >= j) second[p++] = sa[i] - j;
      for (i = 0; i < n; ++i) wv[i] = first[second[i]];
      for (i = 0; i < m; ++i) wt[i] = 0;
      for (i = 0; i < n; ++i) wt[wv[i]]++;
      for (i = 1; i < m; ++i) wt[i] += wt[i - 1];
      for (i = n - 1; i >= 0; --i) sa[--wt[wv[i]]] = second[i];
      for (t = first, first = second, second = t, p = 1, first[sa[0]] = 0,
          i = 1;
           i < n; i++)
        first[sa[i]] = cmp(second, sa[i - 1], sa[i], j) ? p - 1 : p++;
    }
    calhei(r);
    return;
  }
  void calhei(int *r) {
    int i, j, k = 0;
    for (i = 1; i <= n; ++i) rank[sa[i]] = i;
    for (i = 0; i < n; h[rank[i++]] = k)
      for (k ? k-- : 0, j = sa[rank[i] - 1]; r[i + k] == r[j + k]; k++)
        ;
    for (int i = 0; i < n; ++i) {
      sa[i] = sa[i + 1];
      h[i] = h[i + 1];
      rank[i]--;
    }
    rmq.init(n, h);
    return;
  }
  int lcp(int a, int b) {
    if (a == b) return n - a;
    a = rank[a];
    b = rank[b];
    if (a > b) std::swap(a, b);
    return rmq.query(a + 1, b);
  }
} sa;
long long ans;
int L;
pair<int, int> bn[Max_N];
int lens[Max_N], an[Max_N], cost[Max_N], suffix_cost[Max_N], right___t[Max_N];
int len_per_suffix[Max_N];
long long suffix_cost_pre_sum[Max_N];
char s[Max_N];
int get_len(int p) { return len_per_suffix[sa.sa[p]]; }
long long get_cost_sum(int l, int r) {
  if (l) return suffix_cost_pre_sum[r] - suffix_cost_pre_sum[l - 1];
  return suffix_cost_pre_sum[r];
}
void erase(int l, int r, set<pair<int, int> > &pos) {
  pos.erase(pair<int, int>(l, r));
  ds.erase(get_cost_sum(l, r), l, r);
}
void insert(int l, int r, set<pair<int, int> > &pos) {
  if (l == r) {
    bool flag = 1;
    int leng = get_len(l);
    if (l && leng == sa.h[l]) flag = 0;
    if (l < L - 1 && leng == sa.h[l + 1]) flag = 0;
    if (flag) {
      chmax(ans, 1ll * leng * suffix_cost[l]);
    }
  } else {
    pos.insert(pair<int, int>(l, r));
    ds.insert(get_cost_sum(l, r), l, r);
  }
}
void partition(int l, int r, int m, set<pair<int, int> > &pos) {
  erase(l, r, pos);
  insert(l, m - 1, pos);
  insert(m, r, pos);
}
int main() {
  int n;
  cin >> n;
  L = 0;
  bool test_flag = true;
  for (int i = (0); i < (n); i++) {
    scanf("%s", s);
    if (!(s[0] == 'a' && s[1] == 'a' && s[2] == 'a' && s[3] == 'a' &&
          s[4] == 'a'))
      test_flag = false;
    int l = strlen(s);
    lens[i] = l;
    for (int j = (0); j < (l); j++) {
      an[L + j] = s[j] - 'a' + 1;
      len_per_suffix[L + j] = l - j;
    }
    an[L + l] = 27 + i;
    len_per_suffix[L + l] = 0;
    L += l + 1;
  }
  ans = 0;
  long long cost_sum = 0;
  for (int i = (0); i < (n); i++) {
    scanf("%d", cost + i);
    cost_sum += cost[i];
  }
  sa.init(an, L, 27 + n);
  for (int idx = 0, i = 0; i < n; ++i) {
    for (int j = (0); j < (lens[i]); j++) {
      suffix_cost[sa.rank[idx++]] = cost[i];
    }
    suffix_cost[sa.rank[idx++]] = 0;
  }
  suffix_cost_pre_sum[0] = suffix_cost[0];
  for (int i = (1); i < (L); i++)
    suffix_cost_pre_sum[i] = suffix_cost_pre_sum[i - 1] + suffix_cost[i];
  for (int i = (0); i < (L); i++) {
    int l = get_len(i);
    bool flag = true;
    if (i && sa.h[i] == l) flag = false;
    if (i < L - 1 && sa.h[i + 1] == l) flag = false;
    if (flag) chmax(ans, 1ll * l * suffix_cost[i]);
  }
  for (int i = (1); i < (L); i++) bn[i - 1] = pair<int, int>(sa.h[i], i);
  sort(bn, bn + L - 1);
  ds.init();
  set<pair<int, int> > pos;
  insert(0, L - 1, pos);
  int last = -1;
  for (int i = (0); i < (L - 1); i++) {
    if (bn[i].first != last) {
      chmax(ans, 1ll * bn[i].first * ds.get_max());
      last = bn[i].first;
    }
    auto p = --(pos.upper_bound(pair<int, int>(bn[i].second, -1)));
    int l = p->first, r = p->second;
    partition(l, r, bn[i].second, pos);
  }
  cout << ans << endl;
  return 0;
}