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>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
static void redirect(int argc, const char **argv) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  if (argc > 1) {
    static filebuf f;
    f.open(argv[1], ios::in);
    cin.rdbuf(&f);
    if (!cin) {
      cerr << "Failed to open '" << argv[1] << "'" << endl;
      exit(1);
    }
  }
  if (argc > 2) {
    static filebuf f;
    f.open(argv[2], ios::out | ios::trunc);
    cout.rdbuf(&f);
    if (!cout) {
      cerr << "Failed to open '" << argv[2] << "'" << endl;
    }
  }
  cin.exceptions(ios::failbit);
}
struct SATmpEntry {
  int str;
  int ofs;
  std::array<int, 2> rank;
  constexpr SATmpEntry(int str, int ofs, int r)
      : str(str), ofs(ofs), rank{{r, 0}} {}
  constexpr bool operator<(const SATmpEntry &other) const {
    return std::tie(rank, str, ofs) < tie(other.rank, other.str, other.ofs);
  }
};
template <typename Char>
struct SAInit {
  Char value;
  int str;
  int ofs;
  constexpr SAInit(Char value, int str, int ofs)
      : value(value), str(str), ofs(ofs) {}
  constexpr bool operator<(const SAInit &other) const {
    return value < other.value;
  }
};
struct SAEntry {
  int str;
  int ofs;
  int share;
};
template <typename Container>
std::vector<SAEntry> make_suffix_array(const Container &strings) {
  int N = strings.size();
  std::vector<std::vector<int>> rank(N), subrank(N);
  rank.resize(N);
  subrank.resize(N);
  int ae = 0;
  int mchars = 0;
  for (int i = 0; i < N; i++) {
    int sz = strings[i].size() + 1;
    rank[i].resize(sz);
    subrank[i].resize(sz);
    ae += sz;
    mchars = std::max(mchars, int(strings[i].size()));
  }
  std::vector<SAInit<typename Container::value_type::value_type>> init;
  init.reserve(ae - N);
  for (int i = 0; i < N; i++)
    for (int j = 0; j < int(strings[i].size()); j++)
      init.emplace_back(strings[i][j], i, j);
  std::sort(init.begin(), init.end());
  std::vector<SATmpEntry> order;
  order.reserve(ae);
  int irank = 0;
  for (int i = 0; i < N; i++)
    order.emplace_back(i, int(strings[i].size()), irank++);
  for (std::size_t i = 0; i < init.size(); i++) {
    if (i > 0 && init[i - 1] < init[i]) irank++;
    order.emplace_back(init[i].str, init[i].ofs, irank);
  }
  assert(((long long)(order).size()) == ae);
  for (int step = 1; step <= mchars; step *= 2) {
    for (const auto &e : order) rank[e.str][e.ofs] = e.rank[0];
    for (auto &e : order) {
      int L = strings[e.str].size();
      e.rank[1] = rank[e.str][std::min(e.ofs + step, L)];
    }
    sort(order.begin(), order.end());
    std::array<int, 2> prev{{-1, -1}};
    irank = -1;
    for (auto &e : order) {
      if (e.rank != prev) irank++;
      prev = e.rank;
      e.rank[0] = irank;
    }
  }
  std::vector<SAEntry> ans(ae);
  for (int i = 0; i < ae; i++) {
    rank[order[i].str][order[i].ofs] = i;
    ans[i].str = order[i].str;
    ans[i].ofs = order[i].ofs;
  }
  for (int i = 0; i < N; i++) {
    int s = 0;
    int L = strings[i].size();
    for (int j = 0; j <= L; j++) {
      s--;
      if (s < 0) s = 0;
      int p = rank[i][j];
      if (p > 0) {
        const int pi = ans[p - 1].str;
        const int pj = ans[p - 1].ofs;
        const int pL = strings[pi].size();
        while (j + s < L && pj + s < pL &&
               strings[i][j + s] == strings[pi][pj + s])
          s++;
      } else
        s = 0;
      ans[p].share = s;
    }
  }
  return ans;
}
static void solve() {
  int N;
  cin >> N;
  vector<string> t(N);
  for (int i = 0; i < N; i++) cin >> t[i];
  vector<long long> c(N);
  long long ans = 0;
  for (int i = 0; i < N; i++) cin >> c[i];
  auto sa = make_suffix_array(t);
  vector<long long> csum(((long long)(sa).size()) + 1);
  for (int i = 0; i < ((long long)(sa).size()); i++)
    csum[i + 1] = csum[i] + c[sa[i].str];
  vector<pair<int, int>> ranges;
  for (int i = 1; i < ((long long)(sa).size()); i++) {
    int sid = sa[i].str;
    int sh = sa[i].share;
    int start = i;
    while (!ranges.empty() && ranges.back().second > sh) {
      ans = max(ans,
                ranges.back().second * (csum[i] - csum[ranges.back().first]));
      start = ranges.back().first;
      ranges.pop_back();
    }
    if (ranges.empty() || ranges.back().second < sh)
      ranges.emplace_back(start, sh);
    int len = ((long long)(t[sid]).size()) - sa[i].ofs;
    if (sh < len) ranges.emplace_back(i, len);
  }
  while (!ranges.empty()) {
    ans = max(ans,
              ranges.back().second * (csum.back() - csum[ranges.back().first]));
    ranges.pop_back();
  }
  cout << ans << '\n';
}
int main(int argc, const char **argv) {
  redirect(argc, argv);
  solve();
  return 0;
}