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;
struct Node {
  int l, r, link, parent;
  map<int, int> next;
  Node(int l = 0, int r = 0, int p = 0) : l(l), r(r), parent(p), link(-1) {}
  int& operator[](int i) {
    if (!next.count(i)) {
      next[i] = -1;
    }
    return next[i];
  }
};
struct State {
  int v, pos;
  State(int v, int pos) : v(v), pos(pos) {}
  bool operator!=(const State& s) const { return v != s.v || pos != s.pos; }
  bool operator==(const State& s) const { return !(*this != s); }
};
const static State NIL(-1, -1);
const int N = 1e6 + 10;
Node node[2 * N];
int size;
int s[N];
inline int Len(int v) { return node[v].r - node[v].l; }
int AddVertex(int l, int r, int p) {
  node[size] = Node(l, r, p);
  node[p][s[l]] = size;
  return size++;
}
int Split(State st) {
  if (st == NIL) throw int();
  if (st.pos == 0) return node[st.v].parent;
  if (st.pos == Len(st.v)) return st.v;
  int mid = AddVertex(node[st.v].l, node[st.v].l + st.pos, node[st.v].parent);
  node[mid][s[node[st.v].l + st.pos]] = st.v;
  node[st.v].parent = mid;
  node[st.v].l += st.pos;
  return mid;
}
State Go(State st, int l, int r) {
  while (l < r) {
    if (st.pos == Len(st.v)) {
      if (!node[st.v].next.count(s[l])) return NIL;
      st = State(node[st.v].next[s[l]], 0);
    } else {
      if (s[node[st.v].l + st.pos] != s[l]) return NIL;
      int d = min(Len(st.v) - st.pos, r - l);
      l += d;
      st.pos += d;
    }
  }
  return st;
}
int Link(int v) {
  if (node[v].link == -1) {
    if (v == 0) return 0;
    int p = node[v].parent;
    node[v].link = Split(Go(State(Link(p), Len(Link(p))),
                            node[v].l + (p == 0 ? 1 : 0), node[v].r));
  }
  return node[v].link;
}
State TreeExpand(State now, const int i, const int n) {
  while (true) {
    State next = Go(now, i, i + 1);
    if (next != NIL) {
      return next;
    }
    int mid = Split(now);
    AddVertex(i, n, mid);
    if (mid == 0) return now;
    now = State(Link(mid), Len(Link(mid)));
  }
}
void MakeTree(const int n) {
  size = 0;
  node[size++] = Node(0, 0, 0);
  State now(0, 0);
  for (int idx = 0; idx < n; ++idx) {
    now = TreeExpand(now, idx, n);
  }
}
long long ans;
set<pair<int, int> > pos;
long long dfs(int v, int ln) {
  long long sum = 0;
  auto it = pos.lower_bound(make_pair(node[v].l, -1011111111));
  if (it != pos.end() && it->first < node[v].r) {
    sum += it->second;
    if (it->first > node[v].l) {
      ln += it->first - node[v].l;
      ans = max(ans, ln * sum);
    }
    return sum;
  }
  ln += Len(v);
  for (auto nt : node[v].next) {
    sum += dfs(nt.second, ln);
  }
  ans = max(ans, ln * sum);
  return sum;
}
int C[N];
string S[N];
int main() {
  int M;
  scanf("%d", &M);
  for (int _n(M), i(0); i < _n; i++) cin >> S[i];
  for (int _n(M), i(0); i < _n; i++) scanf("%d", C + i);
  int n = 0;
  for (int _n(M), i(0); i < _n; i++) {
    for (int _n((int)S[i].size()), j(0); j < _n; j++)
      s[n++] = int(S[i][j] - 'a');
    pos.emplace(n, C[i]);
    s[n++] = 333 + i;
  }
  MakeTree(n);
  ans = 0;
  dfs(0, 0);
  cout << ans << endl;
  return 0;
}