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 N = 5e5 + 100;
struct State {
  int link, len;
  long long cnt;
  map<char, int> next;
  State(int link, int len, long long cnt) : link(link), len(len), cnt(cnt) {}
  State() : State(0, 0, 0) {}
};
State st[2 * N];
int size, last;
void Init() {
  for (int _n(2 * N), i(0); i < _n; i++) st[i] = State();
  size = last = 0;
  st[0].link = -1;
  ++size;
}
void sa_extend(char c) {
  int p = last;
  if (st[p].next.count(c)) {
    int q = st[p].next[c];
    if (st[q].len == st[p].len + 1) {
      last = q;
      return;
    }
    int clone = size++;
    st[clone] = st[q];
    st[clone].len = st[p].len + 1;
    st[clone].cnt = 0;
    for (; p != -1 && st[p].next[c] == q; p = st[p].link) st[p].next[c] = clone;
    last = clone;
    st[q].link = clone;
    return;
  }
  int cur = size++;
  st[cur].len = st[last].len + 1;
  for (; p != -1 && !st[p].next.count(c); p = st[p].link) st[p].next[c] = cur;
  if (p == -1)
    st[cur].link = 0;
  else {
    int q = st[p].next[c];
    if (st[p].len + 1 == st[q].len)
      st[cur].link = q;
    else {
      int clone = size++;
      st[clone] = st[q];
      st[clone].cnt = 0;
      st[clone].len = st[p].len + 1;
      for (; p != -1 && st[p].next[c] == q; p = st[p].link)
        st[p].next[c] = clone;
      st[q].link = st[cur].link = clone;
    }
  }
  last = cur;
}
string s[N];
vector<int> g[N];
int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  for (int _n(n), i(0); i < _n; i++) cin >> s[i];
  Init();
  for (int _n(n), i(0); i < _n; i++) {
    int cost;
    cin >> cost;
    for (char c : s[i]) {
      sa_extend(c);
      st[last].cnt += cost;
    }
    last = 0;
  }
  for (int _n(size), i(1); i < _n; i++) g[st[i].len].push_back(i);
  long long ans = 0;
  for (int i = N - 1; i >= 0; --i) {
    for (auto v : g[i]) {
      st[st[v].link].cnt += st[v].cnt;
      ans = max(ans, st[v].cnt * st[v].len);
    }
  }
  cout << ans << endl;
  return 0;
}