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 INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fll;
vector<int> suffix_array(string s) {
  s += '$';
  int n = s.size(), N = max(n, 260), ct = 0, k = 0;
  vector<int> p(n), sa(n);
  for (int i = 0; i < n; i++) sa[i] = i, p[i] = s[i];
  while (k < n) {
    vector<int> b(N), nsa(n), np(n);
    for (int i = 0; i < n; i++) b[p[(i - k + n) % n]]++;
    for (int i = 1; i < N; i++) b[i] += b[i - 1];
    for (int i = n - 1; i >= 0; i--)
      nsa[--b[p[(sa[i] - k + n) % n]]] = (sa[i] - k + n) % n;
    sa = nsa, ct = 0;
    pair<int, int> prev, cur;
    for (int i = 0; i < n; i++) {
      cur = {p[sa[i]], p[(sa[i] + k) % n]};
      if (i and prev != cur) ct++;
      np[sa[i]] = ct, prev = cur;
    }
    p = np, k = (k ? 2 * k : 1);
  }
  return vector<int>(sa.begin() + 1, sa.end());
}
vector<long long> flcp(string s, vector<int> sa) {
  int n = s.size(), k = 0;
  vector<int> p(n);
  vector<long long> lcp(n);
  for (int i = 0; i < n; i++) p[sa[i]] = i;
  for (int i = 0; i < n - 1; i++)
    if (p[i]) {
      int j = sa[p[i] - 1];
      while (s[i + k] == s[j + k]) k++;
      lcp[p[i]] = k, k = max(k - 1, 0);
    }
  return vector<long long>(lcp.begin() + 1, lcp.end());
}
template <typename T>
struct rmq {
  vector<T> v;
  int n;
  static const int b = 30;
  vector<int> mask, t;
  int op(int x, int y) { return v[x] < v[y] ? x : y; }
  int msb(int x) { return __builtin_clz(1) - __builtin_clz(x); }
  int small(int r, int sz = b) { return r - msb(mask[r] & ((1 << sz) - 1)); }
  rmq(const vector<T>& v_) : v(v_), n(v.size()), mask(n), t(n) {
    for (int i = 0, at = 0; i < n; mask[i++] = at |= 1) {
      at = (at << 1) & ((1 << b) - 1);
      while (at and op(i, i - msb(at & -at)) == i) at ^= at & -at;
    }
    for (int i = 0; i < n / b; i++) t[i] = small(b * i + b - 1);
    for (int j = 1; (1 << j) <= n / b; j++)
      for (int i = 0; i + (1 << j) <= n / b; i++)
        t[n / b * j + i] =
            op(t[n / b * (j - 1) + i], t[n / b * (j - 1) + i + (1 << (j - 1))]);
  }
  pair<int, T> query(int l, int r) {
    if (r - l + 1 <= b) return {small(r, r - l + 1), v[small(r, r - l + 1)]};
    int ans = op(small(l + b - 1), small(r));
    int x = l / b + 1, y = r / b - 1;
    if (x <= y) {
      int j = msb(y - x + 1);
      ans = op(ans, op(t[n / b * j + x], t[n / b * j + y - (1 << j) + 1]));
    }
    return {ans, v[ans]};
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<string> v(n);
  string t;
  vector<int> interr(n);
  int pos = 0;
  for (int i = 0; i < n; i++) {
    cin >> v[i];
    t += v[i];
    interr[i] = pos + v[i].size() - 1;
    if (i < n - 1) t += '%';
    pos += v[i].size() + 1;
  }
  vector<long long> c(n);
  for (long long& i : c) cin >> i;
  vector<int> sa = suffix_array(t);
  vector<long long> lcp = flcp(t, sa);
  sa = vector<int>(sa.begin() + n - 1, sa.end());
  lcp = vector<long long>(lcp.begin() + n - 1, lcp.end());
  vector<int> w(sa.size());
  vector<int> ssz(sa.size());
  vector<long long> prefsum(sa.size());
  for (int i = 0; i < sa.size(); i++) {
    w[i] = lower_bound(interr.begin(), interr.end(), sa[i]) - interr.begin();
    ssz[i] = interr[w[i]] - sa[i] + 1;
    prefsum[i] = c[w[i]];
    if (i) prefsum[i] += prefsum[i - 1];
  }
  for (int i = 0; i < lcp.size(); i++) {
    lcp[i] = min({(int)lcp[i], ssz[i], ssz[i + 1]});
  }
  auto sum = [&](int l, int r) {
    long long ret = prefsum[r];
    if (l) ret -= prefsum[l - 1];
    return ret;
  };
  rmq<long long> rrmq(lcp);
  function<long long(int, int, int)> solve = [&](int l, int r, int before) {
    int sz = r - l + 2;
    if (sz < 0) return 0LL;
    if (sz == 1) {
      int ww = w[l];
      long long ret = (ssz[l] > before ? c[ww] * ssz[l] : 0LL);
      return ret;
    }
    auto [ppos, mini] = rrmq.query(l, r);
    long long ret = 0;
    if (mini > before) ret = max(ret, mini * sum(l, r + 1));
    ret = max(ret, solve(l, ppos - 1, mini));
    ret = max(ret, solve(ppos + 1, r, mini));
    return ret;
  };
  cout << solve(0, lcp.size() - 1, -1) << '\n';
  return 0;
}