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;
template <class T1, class T2, class T3 = hash<T1>>
using umap = unordered_map<T1, T2, T3>;
template <class T>
using uset = unordered_set<T>;
template <class T>
using vec = vector<T>;
const long long infll = numeric_limits<long long>::max() >> 1;
const long long inf = numeric_limits<long long>::max() >> 1;
const long long N = 1e6 + 50;
long long n, cur, lst, ans;
long long c[N];
string s[N];
vec<long long> len[N];
struct State {
  long long cnt;
  long long link;
  long long leng;
  map<char, long long> adj;
} state[N];
void input() {
  cin >> n;
  for (long long i = 0; i < n; ++i) {
    cin >> s[i];
  }
  for (long long i = 0; i < n; ++i) {
    cin >> c[i];
  }
}
void add_letter(char c) {
  if (state[lst].adj[c] &&
      state[lst].leng + 1 == state[state[lst].adj[c]].leng) {
    lst = state[lst].adj[c];
    return;
  }
  long long p = lst;
  lst = ++cur;
  state[lst].leng = state[p].leng + 1;
  for (; state[p].adj[c] == 0; p = state[p].link) {
    state[p].adj[c] = lst;
  }
  if (state[p].adj[c] == lst) {
    return;
  }
  int q = state[p].adj[c];
  if (state[q].leng == state[p].leng + 1) {
    state[lst].link = q;
    return;
  }
  int r = ++cur;
  state[r].adj = state[q].adj;
  state[r].link = state[q].link;
  state[r].leng = state[p].leng + 1;
  state[q].link = state[lst].link = r;
  for (; state[p].adj[c] == q; p = state[p].link) {
    state[p].adj[c] = r;
  }
}
long long extend(char c) {
  if (state[lst].adj[c] &&
      (state[state[lst].adj[c]].leng = state[lst].leng + 1)) {
    return state[lst].adj[c];
  }
  long long ind = ++cur;
  state[ind].leng = state[lst].leng + 1;
  long long p = lst;
  while (p != -1 && !state[p].adj[c]) {
    state[p].adj[c] = ind;
    p = state[p].link;
  }
  if (p == -1) {
    return ind;
  }
  long long q = state[p].adj[c];
  if (state[q].leng == state[p].leng + 1) {
    state[ind].link = q;
  } else {
    long long r = ++cur;
    state[r] = state[q];
    state[r].cnt = 0;
    state[r].leng = state[p].leng + 1;
    state[q].link = state[ind].link = r;
    while (p != -1 && state[p].adj[c] == q) {
      state[p].adj[c] = r;
      p = state[p].link;
    }
  }
  return ind;
}
void solve() {
  for (long long i = 0; i < n; ++i) {
    for (char x : s[i]) {
      add_letter(x);
      state[lst].cnt += c[i];
    }
    lst = 0;
  }
  for (long long i = 0; i <= cur; ++i) {
    len[state[i].leng].push_back(i);
  }
  for (long long i = N - 1; i >= 1; --i) {
    for (long long u : len[i]) {
      state[state[u].link].cnt += state[u].cnt;
      ans = max(ans, state[u].cnt * state[u].leng);
    }
  }
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  input();
  solve();
}