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;
std::mt19937 rng(
    (long long)std::chrono::steady_clock::now().time_since_epoch().count());
inline long long mod(long long n, long long m) {
  long long ret = n % m;
  if (ret < 0) ret += m;
  return ret;
}
long long gcd(long long a, long long b) {
  return (b == 0LL ? a : gcd(b, a % b));
}
long long exp(long long b, long long e, long long m) {
  b %= m;
  long long ans = 1;
  for (; e; b = b * b % m, e /= 2)
    if (e & 1) ans = ans * b % m;
  return mod(ans, m);
}
struct SuffixArray {
  vector<long long> sa, lcp;
  SuffixArray() {}
  SuffixArray(string& s, long long lim = 256) {
    long long n = ((long long)s.size()) + 1, k = 0, a, b;
    vector<long long> x(s.begin(), s.end() + 1), y(n), ws(max(n, lim)), rank(n);
    sa = lcp = y, iota(sa.begin(), sa.end(), 0);
    for (long long j = 0, p = 0; p < n; j = max(1ll, j * 2), lim = p) {
      p = j, iota(y.begin(), y.end(), n - j);
      for (long long i = 0; i < (n); ++i)
        if (sa[i] >= j) y[p++] = sa[i] - j;
      fill(ws.begin(), ws.end(), 0);
      for (long long i = 0; i < (n); ++i) ws[x[i]]++;
      for (long long i = 1; i < (lim); ++i) ws[i] += ws[i - 1];
      for (long long i = n; i--;) sa[--ws[x[y[i]]]] = y[i];
      swap(x, y), p = 1, x[sa[0]] = 0;
      for (long long i = 1; i < (n); ++i)
        a = sa[i - 1], b = sa[i],
        x[b] = (y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++;
    }
    for (long long i = 1; i < (n); ++i) rank[sa[i]] = i;
    for (long long i = 0, j; i < n - 1; lcp[rank[i++]] = k)
      for (k &&k--, j = sa[rank[i] - 1]; s[i + k] == s[j + k]; k++)
        ;
  }
};
const long long N = 600100;
long long rev[N];
long long ini[N], fim[N];
long long c[N];
long long pai[N], sz[N];
long long f(long long x) { return pai[x] = (pai[x] == x ? x : f(pai[x])); }
long long cost[N];
void join(long long a, long long b) {
  a = f(a);
  b = f(b);
  if (a == b) return;
  if (sz[a] > sz[b]) swap(a, b);
  pai[a] = b;
  sz[b] += sz[a];
  cost[b] += cost[a];
}
long long C[N];
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long n;
  cin >> n;
  string tot = "";
  for (long long i = 0; i < n; i++) {
    string t;
    cin >> t;
    ini[i] = ((long long)tot.size());
    tot += t;
    fim[i] = ((long long)tot.size()) - 1;
    tot += '#';
  }
  assert(((long long)tot.size()) < N);
  for (long long i = 0; i < n; i++) {
    cin >> c[i];
  }
  SuffixArray sa(tot);
  for (long long i = 0; i <= ((long long)tot.size()); i++) {
    if (tot[sa.sa[i]] == '#') sa.lcp[i] = 0;
    rev[sa.sa[i]] = i;
  }
  long long res = 0;
  for (long long i = 0; i < n; i++) {
    long long tam = fim[i] - ini[i] + 1;
    for (long long j = ini[i]; j <= fim[i]; j++) {
      C[rev[j]] = c[i];
      long long pos = rev[j];
      sa.lcp[pos] = min(sa.lcp[pos], (fim[i] - j + 1));
      if (sa.lcp[rev[j]] < (fim[i] - j + 1) and
          (rev[j] == ((long long)tot.size()) ||
           sa.lcp[rev[j] + 1] < (fim[i] - j + 1))) {
        res = max(res, c[i] * (long long)(fim[i] - j + 1));
      }
    }
  }
  vector<pair<long long, long long> > vec;
  for (long long i = 0; i <= ((long long)tot.size()); i++) {
    if (i) vec.push_back(pair<long long, long long>(sa.lcp[i], i));
    pai[i] = i;
    sz[i] = 1;
    cost[i] = C[i];
  }
  sort(vec.begin(), vec.end());
  reverse(vec.begin(), vec.end());
  const long long DB = 0;
  if (DB) {
    cerr << tot << "\n";
    for (long long i = 0; i <= ((long long)tot.size()); i++) {
      cerr << i << " " << sa.sa[i] << " " << tot.substr(sa.sa[i]) << "\n";
    }
  }
  for (long long it = 0; it < ((long long)vec.size());) {
    long long lcp = vec[it].first;
    long long L = it;
    while (it < ((long long)vec.size()) and vec[it].first == lcp) {
      long long id = vec[it].second;
      it++;
      if (tot[sa.sa[id]] == '#' || lcp == 0) continue;
      join(id, id - 1);
    }
    if (lcp == 0) lcp = 1;
    while (L < it) {
      long long id = vec[L++].second;
      if (tot[sa.sa[id]] == '#') continue;
      long long tam = sz[f(id)];
      res = max(res, (lcp)*cost[f(id)]);
      if (DB)
        cerr << id << " " << tam << " " << lcp << " " << cost[f(id)] << "\n";
    }
  }
  cout << res << "\n";
}