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 <class T>
bool ckmax(T& x, T y) {
  return x < y ? x = y, 1 : 0;
}
template <class T>
bool ckmin(T& x, T y) {
  return x > y ? x = y, 1 : 0;
}
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = 0;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return f ? x : -x;
}
const int N = 500005;
const int S = N << 1;
int n, a[N];
string str[N];
int trans[S][26], mxlen[S], link[S], rt[S], tot = 1;
vector<int> e[S];
long long s[S], ans = -1e18;
int extend(int c, int lst, int id) {
  if (trans[lst][c]) {
    int p = lst, q = trans[p][c];
    if (mxlen[p] + 1 == mxlen[q])
      return s[q] += a[id], q;
    else {
      int nq = ++tot;
      mxlen[nq] = mxlen[p] + 1;
      for (int i = 0; i < 26; ++i) trans[nq][i] = trans[q][i];
      link[nq] = link[q], link[q] = nq;
      for (; p && trans[p][c] == q; p = link[p]) trans[p][c] = nq;
      return s[nq] += a[id], nq;
    }
  }
  int p = lst, np = ++tot;
  mxlen[np] = mxlen[p] + 1;
  for (; p && !trans[p][c]; p = link[p]) trans[p][c] = np;
  if (!p)
    link[np] = 1;
  else {
    int q = trans[p][c];
    if (mxlen[p] + 1 == mxlen[q])
      link[np] = q;
    else {
      int nq = ++tot;
      mxlen[nq] = mxlen[p] + 1;
      for (int i = 0; i < 26; ++i) trans[nq][i] = trans[q][i];
      link[nq] = link[q], link[q] = link[np] = nq;
      for (; p && trans[p][c] == q; p = link[p]) trans[p][c] = nq;
    }
  }
  return s[np] += a[id], np;
}
void dfs(int u) {
  for (int v : e[u]) dfs(v), s[u] += s[v];
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 1, iend = n; i <= iend; ++i) cin >> str[i];
  for (int i = 1, iend = n; i <= iend; ++i) cin >> a[i];
  for (int i = 1, iend = n; i <= iend; ++i) {
    int lst = 1, len = (int)(str[i]).size();
    for (int j = 0; j < len; ++j) lst = extend(str[i][j] - 'a', lst, i);
  }
  for (int i = 1; i <= tot; ++i) e[link[i]].push_back(i);
  dfs(1);
  for (int i = 1; i <= tot; ++i) ckmax(ans, 1ll * mxlen[i] * s[i]);
  cout << ans << '\n';
}