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 int inf = 1e9;
const long long inf64 = 1e18;
struct SuffixTree {
  struct Node {
    int l, r, link, par;
    unordered_map<int, int> nxt;
    Node() : l(-1), r(-1), link(-1), par(-1) {}
    Node(int _l, int _r, int _link, int _par)
        : l(_l), r(_r), link(_link), par(_par) {}
    int& next(int c) {
      if (!nxt.count(c)) nxt[c] = -1;
      return nxt[c];
    }
    int get_len() const { return r - l; }
  };
  struct State {
    int v, len;
  };
  vector<Node> t;
  State cur_state;
  vector<int> s;
  SuffixTree() : cur_state({0, 0}) { t.emplace_back(); }
  State go(State st, int l, int r) {
    while (l < r) {
      if (st.len == t[st.v].get_len()) {
        State nx = State({t[st.v].next(s[l]), 0});
        if (nx.v == -1) return nx;
        st = nx;
        continue;
      }
      if (s[t[st.v].l + st.len] != s[l]) return State({-1, -1});
      if (r - l < t[st.v].get_len() - st.len)
        return State({st.v, st.len + r - l});
      l += t[st.v].get_len() - st.len;
      st.len = t[st.v].get_len();
    }
    return st;
  }
  int get_vertex(State st) {
    if (t[st.v].get_len() == st.len) return st.v;
    if (st.len == 0) return t[st.v].par;
    Node& v = t[st.v];
    Node& pv = t[v.par];
    Node add(v.l, v.l + st.len, -1, v.par);
    pv.next(s[v.l]) = (int)t.size();
    add.next(s[v.l + st.len]) = st.v;
    v.par = (int)t.size();
    v.l += st.len;
    t.push_back(add);
    return (int)t.size() - 1;
  }
  int get_link(int v) {
    if (t[v].link != -1) return t[v].link;
    if (t[v].par == -1) return 0;
    int to = get_link(t[v].par);
    to = get_vertex(
        go(State({to, t[to].get_len()}), t[v].l + (t[v].par == 0), t[v].r));
    return t[v].link = to;
  }
  void add_symbol(int c) {
    s.push_back(c);
    while (1) {
      State hlp = go(cur_state, (int)s.size() - 1, (int)s.size());
      if (hlp.v != -1) {
        cur_state = hlp;
        break;
      }
      int v = get_vertex(cur_state);
      Node add((int)s.size() - 1, +inf, -1, v);
      t.push_back(add);
      t[v].next(c) = (int)t.size() - 1;
      cur_state.v = get_link(v);
      cur_state.len = t[cur_state.v].get_len();
      if (!v) break;
    }
  }
};
long long dfs(int v, const vector<vector<int>>& g, const vector<int>& cost,
              const SuffixTree& tree, long long depth, long long& res,
              const vector<pair<int, int>>& sharps) {
  long long sm = 0;
  set<int> dels;
  for (int to : g[v]) {
    const auto& node = tree.t[to];
    int l = node.l;
    int r = min((int)tree.s.size(), node.r);
    auto fnd = lower_bound(sharps.begin(), sharps.end(), make_pair(l, -1));
    if (fnd == sharps.end() || fnd->first >= r) {
      sm += dfs(to, g, cost, tree, depth + r - l, res, sharps);
    } else {
      int pos, symbol;
      tie(pos, symbol) = *fnd;
      if (pos > l) res = max(res, (depth + pos - l) * cost[symbol]);
      if (!dels.count(symbol)) dels.insert(symbol);
      sm += cost[symbol];
    }
  }
  res = max(res, depth * sm);
  return sm;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  SuffixTree tree;
  vector<pair<int, int>> sharps;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    for (char c : s) tree.add_symbol(c - 'a');
    sharps.emplace_back((int)tree.s.size(), i);
    tree.add_symbol(26 + i);
  }
  int sz = (int)tree.t.size();
  vector<int> cost(n);
  for (int i = 0; i < n; i++) cin >> cost[i];
  vector<int> par(sz, -1);
  for (int i = 0; i < sz; i++) {
    const auto& node = tree.t[i];
    par[i] = node.par;
  }
  vector<vector<int>> g(sz);
  for (int i = 0; i < sz; i++)
    if (par[i] != -1) g[par[i]].push_back(i);
  long long res = 0;
  dfs(0, g, cost, tree, 0, res, sharps);
  cout << res << "\n";
  return 0;
}