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;
vector<int> BuildSA(const string &s) {
  int n = (int)s.size();
  vector<pair<pair<int, int>, int>> buff(n);
  vector<int> cl(n);
  for (int _n(n), i(0); i < _n; i++) cl[i] = s[i];
  for (int k = 1; k < n; k *= 2) {
    for (int _n(n), i(0); i < _n; i++)
      buff[i] = make_pair(make_pair(cl[i], cl[(i + k) % n]), i);
    sort((buff).begin(), (buff).end());
    int sz = 0;
    for (int _n(n), i(0); i < _n; i++) {
      if (i == 0 || buff[i].first != buff[i - 1].first) {
        ++sz;
      }
      cl[buff[i].second] = sz - 1;
    }
  }
  vector<int> sa(n);
  for (int _n(n), i(0); i < _n; i++) sa[i] = buff[i].second;
  return sa;
}
vector<int> BuildLCP(const string &s, const vector<int> &sa) {
  int n = (int)s.size();
  vector<int> rnk(n);
  for (int _n(n), i(0); i < _n; i++) rnk[sa[i]] = i;
  vector<int> lcp(n);
  int l = 0;
  for (int _n(n), i(0); i < _n; i++) {
    l = max(0, l - 1);
    if (rnk[i] + 1 < n) {
      int j = sa[rnk[i] + 1];
      while (i + l < n && j + l < n && s[i + l] == s[j + l]) ++l;
    }
    lcp[rnk[i]] = l;
  }
  return lcp;
}
struct Segment {
  int l, r;
  long long val;
  Segment(int l, int r, long long v) : l(l), r(r), val(v) {}
};
bool operator<(Segment a, Segment b) {
  if (a.r == b.r) {
    return a.val < b.val;
  }
  return a.r < b.r;
}
const long long INF = 1e12;
const int N = 1e6 + 10;
string s[N];
int C[N];
int id[N];
int len[N];
vector<int> born[N], toMerge[N];
int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  for (int _n(n), i(0); i < _n; i++) cin >> s[i];
  for (int _n(n), i(0); i < _n; i++) cin >> C[i];
  string al;
  for (int _n(n), i(0); i < _n; i++) {
    al += s[i];
    al += '$';
  }
  int curid = n;
  int curlen = 0;
  for (int i = (int)al.size() - 1; i >= 0; --i) {
    if (al[i] == '$') {
      --curid;
      curlen = 0;
    }
    id[i] = curid;
    len[i] = curlen;
    ++curlen;
  }
  vector<int> sa = BuildSA(al);
  vector<int> lcp(al.size());
  {
    vector<int> tmp = BuildLCP(al, sa);
    for (int _n((int)al.size() - 1), i(0); i < _n; i++) {
      lcp[i] = tmp[i];
    }
  }
  set<Segment> segs;
  multiset<long long> vals;
  long long ans = 0;
  for (int _n((int)al.size()), i(0); i < _n; i++) {
    if (al[sa[i]] != '$') {
      segs.insert(Segment(i, i, -INF));
      vals.insert(-INF);
    }
  }
  for (int _n((int)al.size()), i(0); i < _n; i++) {
    if (al[sa[i]] != '$') {
      born[len[sa[i]]].push_back(i);
      toMerge[lcp[i]].push_back(i);
    }
  }
  for (int i = (int)al.size() - 1; i >= 1; --i) {
    for (int j = 0; j < born[i].size(); ++j) {
      int cur = born[i][j];
      Segment curs = *segs.lower_bound(Segment(cur, cur, -1e18));
      segs.erase(curs);
      vals.erase(vals.find(curs.val));
      curs.val += INF;
      curs.val += C[id[sa[cur]]];
      vals.insert(curs.val);
      segs.insert(curs);
    }
    for (int j = 0; j < toMerge[i].size(); ++j) {
      int cur = toMerge[i][j];
      Segment s1 = *segs.lower_bound(Segment(cur, cur, -1e18));
      segs.erase(s1);
      vals.erase(vals.find(s1.val));
      Segment s2 = *segs.lower_bound(Segment(cur, cur, -1e18));
      segs.erase(s2);
      vals.erase(vals.find(s2.val));
      s1.r = s2.r;
      s1.val += s2.val;
      segs.insert(s1);
      vals.insert(s1.val);
    }
    ans = max(ans, 1LL * i * (*vals.rbegin()));
  }
  cout << ans << endl;
  return 0;
}