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 double pi = acos(-1.0);
const long long mod = 1000000007;
const long long maxn = 1300005;
const long long inf = 1ll << 30;
long long s[maxn];
map<long long, long long> to[maxn];
long long len[maxn], st[maxn], link[maxn], mp[maxn], c[maxn], en[maxn];
long long node, pos, idx, ans;
long long sz = 1, n = 0;
long long make_node(long long _pos, long long _len) {
  st[sz] = _pos;
  len[sz] = _len;
  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(long long c) {
  s[n] = c;
  mp[n++] = idx;
  pos++;
  long long last = 0;
  while (pos > 0) {
    go_edge();
    long long edge = s[n - pos];
    long long &v = to[node][edge];
    long long t = s[st[v] + pos - 1];
    if (v == 0) {
      v = make_node(n - 1, inf);
      link[last] = node;
      last = 0;
    } else if (t == c) {
      link[last] = node;
      return;
    } else {
      long long u = make_node(st[v], pos - 1);
      to[u][c] = make_node(n - 1, inf);
      to[u][t] = v;
      st[v] += pos - 1;
      len[v] -= pos - 1;
      v = u;
      link[last] = u;
      last = u;
    }
    if (node == 0)
      pos--;
    else
      node = link[node];
  }
}
long long dfs(long long node, long long dep) {
  if (to[node].size() == 0) {
    long long id = mp[st[node]];
    long long ret = c[id];
    if (len[node]) ans = max(ans, ret * dep);
    return ret;
  }
  long long ret = 0;
  for (auto i : to[node]) {
    long long next = i.second;
    if (len[next] > maxn) len[next] = en[st[next]];
    ret += dfs(next, dep + len[next]);
  }
  ans = max(ans, ret * dep);
  return ret;
}
void set_ends() {
  for (int i = n - 1; i >= 0; i--) {
    if (s[i] < 26)
      en[i] = en[i + 1] + 1;
    else
      en[i] = 0;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  len[0] = inf;
  long long n;
  cin >> n;
  string s;
  for (long long i = 0; i < n; i++) {
    cin >> s;
    for (auto j : s) {
      add_letter(j - 'a');
    }
    add_letter(26 + i);
    idx++;
  }
  set_ends();
  for (long long i = 0; i < n; i++) {
    cin >> c[i];
  }
  dfs(0, 0);
  cout << ans << "\n";
  return 0;
}