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;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &item) {
  out << '(' << item.first << ", " << item.second << ')';
  return out;
}
template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  for (const auto &item : v) out << item << ' ';
  return out;
}
const int N = 100010;
const int L = 600010;
struct Suff {
  int id;
  pii p;
  bool operator<(const Suff &other) const { return p < other.p; }
};
int p[L], sa[L], lcp[L], l[L], r[L], nextHash[L];
ll cost[N], sac[L];
Suff v[L];
void suffixArray(const string &s) {
  int n = s.length();
  for (int i = 0; i < n; ++i) p[i] = s[i];
  for (int i = 0; (1 << i) < n || !i; ++i) {
    for (int j = 0; j < n; ++j)
      v[j].p = {p[j], j + (1 << i) < n ? p[j + (1 << i)] : -1}, v[j].id = j;
    sort(v, v + n);
    for (int j = 0; j < n; ++j)
      p[v[j].id] = (j && v[j - 1].p == v[j].p ? p[v[j - 1].id] : j);
  }
  int id = 0;
  for (int j = 0; j < n; ++j) {
    sa[p[j]] = j;
    if (s[j] == '#')
      ++id;
    else
      sac[p[j]] = cost[id];
  }
  nextHash[n - 1] = n;
  for (int i = n - 2; i >= 0; --i)
    nextHash[i] = (s[i] == '#' ? i : nextHash[i + 1]);
  for (int i = 0, k = 0; i < n; ++i) {
    if (p[i] == n - 1)
      k = 0;
    else {
      int j = sa[p[i] + 1];
      while (i + k < n && j + k < n && s[i + k] == s[j + k]) ++k;
      lcp[p[i]] = min(k, nextHash[i] - i);
      if (k) --k;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  int n;
  string word, s;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> word;
    if (!s.empty()) s += '#';
    s += word;
  }
  for (int i = 0; i < n; ++i) cin >> cost[i];
  suffixArray(s);
  int m = s.length();
  for (int i = 1; i < m; ++i) sac[i] += sac[i - 1];
  stack<int> stk;
  for (int i = 0; i < m - 1; ++i) {
    while (!stk.empty() && lcp[stk.top()] >= lcp[i]) stk.pop();
    l[i] = (stk.empty() ? 0 : stk.top() + 1);
    stk.push(i);
  }
  while (!stk.empty()) stk.pop();
  for (int i = m - 2; i >= 0; --i) {
    while (!stk.empty() && lcp[stk.top()] >= lcp[i]) stk.pop();
    r[i] = (stk.empty() ? m - 2 : stk.top() - 1);
    stk.push(i);
  }
  ll ans = 0;
  for (int i = 0; i < m - 1; ++i) {
    ll sum = sac[r[i] + 1] - (l[i] ? sac[l[i] - 1] : 0);
    ans = max(ans, sum * lcp[i]);
  }
  for (int i = 0, id = 0; i < m; ++i) {
    if (s[i] == '#') {
      ++id;
      continue;
    }
    int sz = 0;
    if (p[i]) sz = max(sz, lcp[p[i] - 1]);
    if (p[i] < m - 1) sz = max(sz, lcp[p[i]]);
    if (sz >= nextHash[i] - i) continue;
    if (i == 77)
      cerr << "sac[i] - sac[i - 1]"
              ": "
           << (sac[i] - sac[i - 1]) << endl;
    ans = max(ans, 1LL * (nextHash[i] - i) * cost[id]);
  }
  cout << ans << '\n';
  return 0;
}