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 T>
inline bool chkmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
const int Mod = 1e9 + 7;
const int maxn = 100000, maxlen = 500000;
int n;
int tot = 0;
int go[(maxlen << 1)][26], fa[(maxlen << 1) + 5], Max[(maxlen << 1) + 5];
int rt = 0;
long long sum[(maxlen << 1) + 5];
long long ans = 0;
inline int add(int p, int w) {
  if (go[p][w] && Max[go[p][w]] == Max[p] + 1) return go[p][w];
  int np = tot++;
  fa[np] = -1;
  Max[np] = Max[p] + 1;
  while (p != -1 && !go[p][w]) go[p][w] = np, p = fa[p];
  if (p == -1)
    fa[np] = rt;
  else {
    int q = go[p][w];
    if (Max[q] == Max[p] + 1)
      fa[np] = q;
    else {
      int nq = tot++;
      fa[nq] = -1;
      Max[nq] = Max[p] + 1;
      memcpy(go[nq], go[q], sizeof go[nq]);
      fa[nq] = fa[q];
      fa[np] = fa[q] = nq;
      while (p != -1 && go[p][w] == q) go[p][w] = nq, p = fa[p];
    }
  }
  return np;
}
vector<int> all[maxlen + 5];
int main() {
  static string s[maxn + 5];
  scanf("%d", &n);
  for (int i = (0), _end_ = (n); i < _end_; ++i) cin >> s[i];
  fa[0] = -1;
  tot = 1;
  int L = 0;
  for (int i = (0), _end_ = (n); i < _end_; ++i) {
    int first;
    scanf("%d", &first);
    int cur = 0;
    for (auto c : s[i]) cur = add(cur, c - 'a'), sum[cur] += first;
    chkmax(L, (int((s[i]).size())));
  }
  for (int i = (0), _end_ = (tot); i < _end_; ++i) all[Max[i]].push_back(i);
  for (int i = L; i >= 1; --i)
    for (auto nd : all[i]) chkmax(ans, i * sum[nd]), sum[fa[nd]] += sum[nd];
  printf("%I64d\n", ans);
  return 0;
}