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;
namespace SuffixTree {
const int INF = 2e9, N = 2 * (int)2e6 + 5, dollar = 257;
int s[N];
map<int, int> to[N];
int len[N] = {INF}, fpos[N], link[N], suff[N], par[N];
int node, pos, remain;
int sz = 1, n = 0;
inline void init() {
  for (int i = 0; i < max(sz, n); i++) {
    len[i] = fpos[i] = link[i] = suff[i] = par[i] = s[i] = 0;
    to[i].clear();
  }
  node = pos = remain = 0;
  sz = 1;
  n = 0;
  len[0] = INF;
}
inline int make_node(int _pos, int _len, int _par) {
  fpos[sz] = _pos;
  len[sz] = _len;
  suff[sz] = n - remain;
  par[sz] = _par;
  return sz++;
}
inline void go_edge() {
  while (pos > len[to[node][s[n - pos]]]) {
    node = to[node][s[n - pos]];
    pos -= len[node];
  }
}
inline void add_letter(int c) {
  s[n++] = c;
  int last = 0;
  for (remain++, pos++; pos > 0; remain--) {
    go_edge();
    int edge = s[n - pos];
    int &v = to[node][edge];
    int t = s[fpos[v] + pos - 1];
    if (v == 0) {
      v = make_node(n - pos, INF, node);
      link[last] = node;
      last = 0;
    } else if (t == c) {
      link[last] = node;
      return;
    } else {
      int u = make_node(fpos[v], pos - 1, node);
      to[u][c] = make_node(n - 1, INF, u);
      to[u][t] = v;
      par[v] = u;
      fpos[v] += pos - 1;
      len[v] -= pos - 1;
      v = u;
      link[last] = u;
      last = u;
    }
    if (node == 0)
      pos--;
    else
      node = link[node];
  }
}
}  // namespace SuffixTree
string s[(int)2e6 + 5];
int doll[(int)2e6 + 5];
int cost[(int)2e6 + 5];
int pos_suf[(int)2e6 + 5];
int n, cnt = 0, sum = 0;
long long res = 0;
inline long long dfs(int c, int length = 0) {
  long long ret = 0;
  if (SuffixTree::len[c] > (int)2e6 + 5) ret = cost[doll[SuffixTree::fpos[c]]];
  for (auto x : SuffixTree::to[c]) {
    int y = x.second;
    bool chk = false;
    int len = SuffixTree::len[y];
    if (len > (int)2e6 + 5) {
      len = pos_suf[SuffixTree::fpos[y]] - SuffixTree::fpos[y];
      chk = (len == 0);
    }
    len += length;
    long long now = dfs(y, len);
    ret += now;
    if (!chk) res = max(res, 1LL * len * now);
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n;
  for (int x = 0; x < n; x++) cin >> s[x];
  for (int x = 0; x < n; x++) {
    int lim = (int)s[x].size();
    sum += lim;
    for (int y = 0; y < lim; y++, cnt++) {
      SuffixTree::add_letter(s[x][y]);
      doll[cnt] = x;
      pos_suf[cnt] = sum;
    }
    SuffixTree::add_letter(257 + x);
    pos_suf[cnt] = sum++;
    doll[cnt++] = x;
  }
  for (int x = 0; x < n; x++) cin >> cost[x];
  dfs(0);
  cout << res << "\n";
}