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 int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
string s[100005];
int nxt[maxn][26], par[maxn], len[maxn], tp[maxn], rk[maxn];
long long sum[maxn];
int n, cnt, last;
int add(int l) {
  ++cnt;
  len[cnt] = l;
  return cnt;
}
void init() {
  cnt = 0;
  last = add(0);
}
void insert(char ch) {
  int t = ch - 'a', p = last, cur;
  if (nxt[p][t]) {
    int q = nxt[p][t];
    if (len[q] == len[p] + 1) {
      last = q;
      return;
    }
    int nq = add(len[p] + 1);
    last = nq;
    memcpy(nxt[nq], nxt[q], sizeof nxt[q]);
    par[nq] = par[q], par[q] = nq;
    while (p && nxt[p][t] == q) nxt[p][t] = nq, p = par[p];
    return;
  }
  cur = last = add(len[p] + 1);
  while (p && !nxt[p][t]) nxt[p][t] = cur, p = par[p];
  if (!p) {
    par[cur] = 1;
    return;
  }
  int q = nxt[p][t];
  if (len[q] == len[p] + 1) {
    par[cur] = q;
    return;
  }
  int nq = add(len[p] + 1);
  memcpy(nxt[nq], nxt[q], sizeof nxt[q]);
  par[nq] = par[q], par[q] = par[cur] = nq;
  while (p && nxt[p][t] == q) nxt[p][t] = nq, p = par[p];
}
void rsort() {
  for (int i = 0; i <= cnt; ++i) tp[i] = 0;
  for (int i = 1; i <= cnt; ++i) ++tp[len[i]];
  for (int i = 1; i <= cnt; ++i) tp[i] += tp[i - 1];
  for (int i = cnt; i >= 1; --i) rk[tp[len[i]]--] = i;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  init();
  for (int i = 1; i <= n; ++i) {
    cin >> s[i];
  }
  for (int i = 1; i <= n; ++i) {
    int c;
    cin >> c;
    for (int j = 0; j < ((int)s[i].size()); ++j) {
      insert(s[i][j]);
      sum[last] += c;
    }
    last = 1;
  }
  rsort();
  long long ret = 0;
  for (int i = cnt; i >= 2; --i) {
    int u = rk[i];
    sum[par[u]] += sum[u];
    ret = max(ret, sum[u] * len[u]);
  }
  cout << ret << endl;
  return 0;
}