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>
inline long long sbt(long long x) { return __builtin_popcount(x); }
using namespace std;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
long long s[1000003];
long long pos[1000003];
long long a[1000003];
long long dp[1000003];
long long ns;
map<long long, long long> adj[1000003];
long long lft[1000003], rgt[1000003];
long long p[1000003];
long long slink[1000003];
long long tv;
long long tp;
long long nd_idx;
long long la;
long long n;
string s11[1000003];
long long k, curr;
pair<long long, long long> boundary[1000003];
void add_leaf_r1(long long c) {
  adj[tv][c] = nd_idx;
  lft[nd_idx] = la;
  p[nd_idx++] = tv;
  tv = slink[tv];
  tp = rgt[tv] + 1;
}
void split_the_edge() {
  lft[nd_idx] = lft[tv];
  rgt[nd_idx] = tp - 1;
  p[nd_idx] = p[tv];
  adj[nd_idx][s[tp]] = tv;
}
void add_c_transition_leaf(long long c) {
  adj[nd_idx][c] = nd_idx + 1;
  lft[nd_idx + 1] = la;
  p[nd_idx + 1] = nd_idx;
}
void go_down() {
  while (tp <= rgt[nd_idx - 2]) {
    tv = adj[tv][s[tp]];
    tp += rgt[tv] - lft[tv] + 1;
  }
}
void st_iteration(long long c) {
slable:;
  if (rgt[tv] < tp) {
    if (tv != 1 && !adj[tv][c]) {
      add_leaf_r1(c);
      goto slable;
    }
    tv = adj[tv][c];
    tp = lft[tv];
  }
  if (tp == -1 || c == s[tp]) {
    tp++;
  } else {
    split_the_edge();
    add_c_transition_leaf(c);
    lft[tv] = tp;
    p[tv] = nd_idx;
    adj[p[nd_idx]][s[lft[nd_idx]]] = nd_idx;
    nd_idx += 2;
    tv = slink[p[nd_idx - 2]];
    tp = lft[nd_idx - 2];
    go_down();
    if (tp == rgt[nd_idx - 2] + 1)
      slink[nd_idx - 2] = tv;
    else
      slink[nd_idx - 2] = nd_idx;
    tp = rgt[tv] - (tp - rgt[nd_idx - 2]) + 2;
    goto slable;
  }
}
void init_st(long long start_idx) {
  tv = 0;
  tp = 0;
  nd_idx = start_idx;
  fill(rgt, rgt + 1000003, n - 1);
  slink[0] = 1;
  for (long long i = 0; i < start_idx; i++) {
    lft[i] = -1;
    rgt[i] = -1;
    if (i) adj[i].clear();
  }
  long long m = n;
  for (la = 0; la < m; la++) st_iteration(s[la]);
}
long long l[1000003];
void dfs(long long i, long long curr) {
  bool isleaf = 1;
  for (auto pnei : adj[i]) {
    long long nei = pnei.second;
    isleaf = 0;
    dfs(nei, curr + rgt[nei] - lft[nei] + (rgt[nei] <= 256));
    dp[i] += dp[nei];
  }
  if (isleaf) {
    l[i] = 1;
    dp[i] = a[pos[s[rgt[i]]]];
  }
}
long long res = 0;
void dfs1(long long i, long long curr) {
  if (l[i]) {
    if (lft[i] != rgt[i]) res = max(res, dp[i] * curr);
    return;
  }
  for (auto pnei : adj[i]) {
    long long nei = pnei.second;
    dfs1(nei, curr + rgt[nei] - lft[nei] + (s[rgt[nei]] <= 256));
  }
  res = max(res, dp[i] * curr);
}
int32_t main() {
  cin.sync_with_stdio(false);
  cout.sync_with_stdio(false);
  ns = 0;
  cin >> ns;
  for (long long i = 0; i < ns; i++) cin >> s11[i];
  for (long long i = 0; i < ns; i++) cin >> a[i];
  long long ld = 0;
  for (long long i = 0; i < s11[0].size(); i++) s[ld++] = int32_t(s11[0][i]);
  for (long long i = 1; i < ns; i++) {
    s[ld++] = 257 + i;
    pos[257 + i] = i - 1;
    for (long long j = 0; j < s11[i].size(); j++) s[ld++] = int32_t(s11[i][j]);
  }
  s[ld++] = 257 + ns;
  pos[257 + ns] = ns - 1;
  n = ld;
  boundary[0] = {0, s11[0].size()};
  vector<long long> starts;
  starts.push_back(0);
  for (long long i = 1; i < ns; i++) {
    boundary[i].first = boundary[i - 1].second + 1;
    boundary[i].second = boundary[i - 1].second + 1 + s11[i].size();
    starts.push_back(boundary[i].first);
  }
  starts.push_back(1000000007);
  init_st(2);
  for (long long i = 2; i < nd_idx; i++) {
    long long st = lft[i];
    long long en = rgt[i];
    long long kis_boundary_mein_st =
        upper_bound(starts.begin(), starts.end(), st) - starts.begin() - 1;
    long long kis_boundary_mein_en =
        upper_bound(starts.begin(), starts.end(), en) - starts.begin() - 1;
    if (kis_boundary_mein_st != kis_boundary_mein_en) {
      en = boundary[kis_boundary_mein_st].second;
    }
    lft[i] = st;
    rgt[i] = en;
  }
  dfs(0, 0);
  dfs1(0, 0);
  cout << res << endl;
  return 0;
}