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 long long inf = 1000007;
const long long maxn = 2000002;
long long mon[maxn], col[maxn], ncol[maxn], sm[maxn], korz[maxn], nsm[maxn];
long long norm(long long a, long long m) { return (a % m + m) % m; }
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long kol_vo;
  long long ans = 0;
  cin >> kol_vo;
  vector<long long> answ;
  long long last = 0;
  vector<string> dd;
  map<string, long long> m;
  for (long long c = 0; c < kol_vo; c++) {
    string s;
    cin >> s;
    dd.push_back(s);
    for (long long i = 0; i < s.size(); i++) {
      answ.push_back(s[i] - 'a' + inf);
    }
    answ.push_back(++last);
  }
  long long y = 0;
  for (long long c = 0; c < kol_vo; c++) {
    cin >> mon[c];
    y += mon[c];
  }
  for (long long c = 0; c < kol_vo; c++) m[dd[c]] += (dd[c].size() * mon[c]);
  for (auto i : m) ans = max(ans, i.second);
  long long len = answ.size();
  vector<pair<long long, long long> > v;
  for (long long c = 0; c < len; c++) {
    v.push_back({answ[c], c});
  }
  sort(v.begin(), v.end());
  long long now = -1;
  for (long long c = 0; c < len; c++) {
    sm[c] = v[c].second;
    if (c == 0 || v[c].first != v[c - 1].first) now++;
    korz[now + 1]++;
    col[sm[c]] = now;
  }
  for (long long i = 1; i < len; i++) korz[i] += korz[i - 1];
  long long l = 1;
  while (l < len) {
    for (long long i = 0; i < len; i++) {
      long long j = norm(sm[i] - l, len);
      nsm[korz[col[j]]++] = j;
    }
    now = 0;
    for (long long i = 0; i < len; i++) {
      if (i == 0 || col[nsm[i]] != col[nsm[i - 1]] ||
          col[norm(nsm[i] + l, len)] != col[norm(nsm[i - 1] + l, len)])
        korz[now++] = i;
      ncol[nsm[i]] = now - 1;
    }
    for (long long i = 0; i < len; i++) {
      sm[i] = nsm[i];
      col[i] = ncol[i];
    }
    l *= 2;
  }
  vector<long long> lcp(len);
  vector<long long> rev(len);
  for (long long c = 0; c < len; c++) rev[sm[c]] = c;
  last = 0;
  for (long long c = 0; c < len; c++) {
    long long i = rev[c];
    if (i == len - 1) continue;
    long long r = sm[i + 1];
    while (answ[c + last] == answ[r + last]) last++;
    lcp[i] = last;
    last--;
    last = max(last, 0ll);
  }
  last = 0;
  vector<long long> llast(len);
  vector<long long> dop(len);
  for (long long c = 0; c < len; c++) {
    if (answ[c] < inf) {
      last++;
      continue;
    }
    llast[rev[c]] = last;
    dop[rev[c]] = mon[last];
  }
  vector<long long> pref(len + 1);
  for (long long c = 1; c <= len; c++) pref[c] = pref[c - 1] + dop[c - 1];
  pref.push_back(pref[pref.size() - 1]);
  stack<long long> st;
  vector<long long> mminl(len);
  for (long long c = 0; c < len; c++) {
    while (!st.empty() && lcp[st.top()] >= lcp[c]) st.pop();
    mminl[c] = st.empty() ? 0 : st.top();
    st.push(c);
  }
  while (!st.empty()) st.pop();
  vector<long long> mminr(len);
  for (long long c = len - 1; c >= 0; c--) {
    while (!st.empty() && lcp[st.top()] >= lcp[c]) st.pop();
    mminr[c] = st.empty() ? len : st.top();
    st.push(c);
  }
  for (long long c = 0; c < len; c++) {
    long long l = mminl[c];
    long long r = mminr[c];
    ans = max(ans, (pref[r + 1] - pref[l + 1]) * lcp[c]);
  }
  cout << ans;
  return 0;
}