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>
template <typename T>
struct SegmentTree {
 private:
  using F = std::function<T(T, T)>;
  int n;
  F f;
  T ti;
  std::vector<T> dat;

 public:
  SegmentTree(){};
  SegmentTree(F f, T ti) : f(f), ti(ti) {}
  void build(int n_) {
    n = n_;
    dat.assign(2 * n, ti);
  }
  void build(const std::vector<T> &v) {
    int n_ = v.size();
    build(n_);
    for (int i = 0; i < n; ++i) dat[n + i] = v[i];
    for (int i = n - 1; i >= 0; --i) dat[i] = f(dat[2 * i + 0], dat[2 * i + 1]);
  }
  void set_val(int k, T x) {
    dat[k += n] = x;
    while (k > 0) {
      k = k / 2;
      dat[k] = f(dat[2 * k + 0], dat[2 * k + 1]);
    }
  }
  T query(int a, int b) {
    if (a == b) return ti;
    T vl = ti, vr = ti;
    for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vl = f(vl, dat[l++]);
      if (r & 1) vr = f(dat[--r], vr);
    }
    return f(vl, vr);
  }
};
using namespace std;
struct SuffixArray {
 private:
  string s;
  size_t size;
  void constructLCPArray() {
    for (size_t i = 0; i < size; ++i) {
      rank[SA[i]] = i;
    }
    int l = 0;
    for (size_t i = 0; i < size; ++i) {
      int idx = rank[i];
      int p1 = SA[idx];
      if (idx + 1 == size) {
        l = 0;
        LCP[idx] = l;
        continue;
      }
      int p2 = SA[idx + 1];
      while (max(p1, p2) + l < size and s[p1 + l] == s[p2 + l]) ++l;
      LCP[idx] = l;
      --l;
      l = max(l, 0);
    }
  }

 public:
  vector<int> SA, LCP, rank;
  SuffixArray(string s_)
      : s(s_),
        size(s_.length() + 1),
        SA(size + 1),
        LCP(size + 1),
        rank(size + 1) {
    s += "$";
  }
  void construct() {
    vector<int> cnt(max((size_t)256, size), 0);
    for (auto e : s) {
      ++cnt[e];
    }
    for (size_t i = 1; i < cnt.size(); ++i) cnt[i] += cnt[i - 1];
    vector<int> p(size);
    for (size_t i = 0; i < size; ++i) {
      p[--cnt[s[i]]] = i;
    }
    vector<int> c(size);
    c[p[0]] = 0;
    for (size_t i = 1; i < size; ++i) {
      c[p[i]] = c[p[i - 1]] + (s[p[i]] != s[p[i - 1]]);
    }
    for (size_t k = 1; k < size; k *= 2) {
      vector<int> p_(size), c_(size);
      for (size_t j = 0; j < size; ++j) {
        p_[j] = p[j] - k;
        if (p_[j] < 0) p_[j] += size;
      }
      fill(cnt.begin(), cnt.end(), 0);
      int max_e = 0;
      for (auto e : c) {
        ++cnt[e], max_e = max(max_e, e);
      }
      for (int i = 0; i < max_e; ++i) {
        cnt[i + 1] += cnt[i];
      }
      for (size_t i = size - 1; i < size; --i) {
        p[--cnt[c[p_[i]]]] = p_[i];
      }
      c_[p[0]] = 0;
      int classes = 1;
      for (size_t i = 1; i < size; ++i) {
        if ((c[p[i]] != c[p[i - 1]]) or
            (c[(p[i] + k) % size] != c[(p[i - 1] + k) % size]))
          ++classes;
        c_[p[i]] = classes - 1;
      }
      swap(c, c_);
    }
    SA = p;
    constructLCPArray();
  }
};
int main() {
  int n;
  cin >> n;
  vector<string> S(n);
  string cat;
  for (int i = 0; i < n; ++i) {
    cin >> S[i];
    cat += S[i] + "$";
  }
  vector<long long> C(n);
  for (int i = 0; i < n; ++i) cin >> C[i];
  int m = cat.length();
  vector<long long> W_(m + 1), L(m + 1);
  int l = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < S[i].length(); ++j) {
      W_[l + j] = C[i];
      L[l + j] = S[i].length() - j;
    }
    l += S[i].length() + 1;
  }
  SuffixArray sa(cat);
  sa.construct();
  vector<int> LCP = sa.LCP;
  auto SA = sa.SA;
  vector<long long> W(m + 1);
  for (int i = 1; i <= m; ++i) {
    W[i] = W_[SA[i]];
    LCP[i - 1] = min<long long>({LCP[i - 1], L[SA[i - 1]], L[SA[i]]});
  }
  for (int i = 0; i < m; ++i) {
    W[i + 1] += W[i];
  }
  const int INF = 1e9;
  function<int(int, int)> f = [](int a, int b) { return min(a, b); };
  SegmentTree<int> st(f, INF);
  st.build(LCP);
  long long ans = 0LL;
  for (int i = 1; i <= m; ++i) {
    if (L[SA[i]] > LCP[i - 1] and LCP[i] < L[SA[i]]) {
      ans = max(ans, (W[i] - W[i - 1]) * L[SA[i]]);
    }
    if (!LCP[i]) {
      continue;
    }
    int l = i, r = i + 1;
    {
      int ok = -1, ng = i + 1;
      while (ng - ok > 1) {
        int mid = (ok + ng) / 2;
        if (st.query(mid, i + 1) == LCP[i])
          ng = mid;
        else
          ok = mid;
      }
      l = ok;
    }
    {
      int ok = i, ng = m + 1;
      while (ng - ok > 1) {
        int mid = (ok + ng) / 2;
        if (st.query(i, mid) == LCP[i])
          ok = mid;
        else
          ng = mid;
      }
      r = ok;
    }
    long long t = LCP[i] * (W[r] - W[l]);
    ans = max(ans, t);
  }
  cout << ans << endl;
}