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 = 1 << 21;
string ss;
long long S[MAXN];
long long m, k, b[MAXN], hh, sz[MAXN], suml[MAXN], sumr[MAXN], ans, len[MAXN];
long long N, gap, sa[MAXN], pos[MAXN], tmp[MAXN], lcp[MAXN];
bool sufCmp(int i, int j) {
  if (pos[i] != pos[j]) return pos[i] < pos[j];
  i += gap;
  j += gap;
  return (i < N && j < N) ? pos[i] < pos[j] : i > j;
}
void buildSA() {
  for (int i = 0; i < N; i++) sa[i] = i, pos[i] = S[i];
  for (gap = 1;; gap *= 2) {
    sort(sa, sa + N, sufCmp);
    for (int i = 0; i < N - 1; i++)
      tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]);
    for (int i = 0; i < N; i++) pos[sa[i]] = tmp[i];
    if (tmp[N - 1] == N - 1) break;
  }
}
void buildLCP() {
  for (int i = 0, k = 0; i < N; ++i)
    if (pos[i] != N - 1) {
      for (int j = sa[pos[i] + 1]; S[i + k] == S[j + k];) ++k;
      lcp[pos[i]] = k;
      if (k) --k;
    }
}
int buf = 1e5;
vector<long long> l, r;
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> m;
  for (int i = 0; i < m; i++) {
    cin >> ss;
    for (int j = 0; j < ss.size(); j++) S[N++] = ss[j];
    S[N++] = buf++;
    sz[i] = ss.size();
  }
  int x;
  for (int i = 0; i < m; i++) {
    cin >> x;
    int k = hh;
    while ('a' <= S[hh] && S[hh] <= 'z') b[hh] = x, hh++;
    hh++;
  }
  buildSA(), buildLCP();
  for (int i = N - 1; i >= 0; i--) {
    len[i] = len[i + 1] + 1;
    if (S[i] < 'a' || S[i] > 'z') len[i] = 0;
  }
  for (int i = 0; i < N; i++) {
    bool f = true;
    if (i && lcp[i - 1] >= len[sa[i]]) f = false;
    if (i < N - 1 && lcp[i] >= len[sa[i]]) f = false;
    if (f) ans = max(ans, len[sa[i]] * b[sa[i]]);
  }
  for (int i = 0; i < N; i++)
    if (S[sa[i]] >= 'a' && S[sa[i]] <= 'z') {
      long long tmp = b[sa[i]];
      while (l.size() && lcp[l.back()] >= lcp[i])
        tmp += suml[l.back()], l.pop_back();
      suml[i] = tmp, l.push_back(i);
    }
  for (int i = N - 1; i >= 0; i--)
    if (S[sa[i]] >= 'a' && S[sa[i]] <= 'z') {
      long long tmp = b[sa[i + 1]];
      while (r.size() && lcp[r.back()] >= lcp[i])
        tmp += sumr[r.back()], r.pop_back();
      sumr[i] = tmp, r.push_back(i);
      ans = max(ans, 1LL * (suml[i] + sumr[i]) * lcp[i]);
    }
  cout << ans;
}