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 <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
const int INF = 1e9;
namespace SuffixTree {
const int MAXN = 2e6;
const int dollar = 257;
int s[MAXN];
map<int, int> to[MAXN];
int len[MAXN] = {INF}, fpos[MAXN], link[MAXN], suff[MAXN], par[MAXN];
int node, pos, remain;
int sz = 1, n = 0;
int make_node(int _pos, int _len, int _par) {
  fpos[sz] = _pos;
  len[sz] = _len;
  suff[sz] = n - remain;
  par[sz] = _par;
  return sz++;
}
void go_edge() {
  while (pos > len[to[node][s[n - pos]]]) {
    node = to[node][s[n - pos]];
    pos -= len[node];
  }
}
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
const int N = int(2e6) + 10;
int cost[N], idx[N], len, dollar[N];
long long int sum[N];
char s[N];
long long int ans;
void dfs(int x, int clen = 0) {
  sum[x] = (SuffixTree::to[x].empty() ? cost[idx[SuffixTree::suff[x]]] : 0);
  for (auto it : SuffixTree::to[x]) {
    int y = it.second, l = SuffixTree::fpos[y],
        r = min(len - 1, l + SuffixTree::len[y] - 1);
    if (clen < 0)
      dfs(y, clen);
    else if (dollar[l] <= r)
      dfs(y, -INF),
          ans = max(ans, sum[y] * (dollar[l] - l + (dollar[l] > l ? clen : 0)));
    else
      dfs(y, clen + r - l + 1);
    sum[x] += sum[y];
  }
  if (clen >= 0) ans = max(ans, sum[x] * clen);
}
int main() {
  int n;
  scanf("%d", &n);
  int prv = 0;
  for (int i = (0); i < (n); ++i) {
    scanf("%s", s);
    for (char* c = s; *c; c++) SuffixTree::add_letter(*c), idx[len++] = i;
    SuffixTree::add_letter(SuffixTree::dollar + i);
    idx[len++] = i;
    for (int j = (prv); j < (len); ++j) dollar[j] = len - 1;
    prv = len;
  }
  for (int i = (0); i < (n); ++i) scanf("%d", &cost[i]);
  dfs(0);
  printf("%lld\n", ans);
}