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>
int dr[] = {2, 2, -2, -2, 1, -1, 1, -1};
int dc[] = {1, -1, 1, -1, 2, 2, -2, -2};
int dr1[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dc1[] = {1, -1, 1, 0, -1, 0, 1, -1};
int dr2[] = {0, 0, 1, -1};
int dc2[] = {1, -1, 0, 0};
using namespace std;
long long int siz, last, occ[1000005], cost[1000005];
struct automata {
  long long int len, link, next[27];
} st[1000005];
void inser(char c, long long int y) {
  long long int now = ++siz;
  st[now].len = st[last].len + 1;
  long long int p, q, cl;
  occ[now] = 1;
  cost[now] = y;
  for (p = last; p != -1 && !st[p].next[c]; p = st[p].link) st[p].next[c] = now;
  if (p == -1)
    st[now].link = 0;
  else {
    q = st[p].next[c];
    if (st[p].len + 1 == st[q].len)
      st[now].link = q;
    else {
      cl = ++siz, st[cl].len = st[p].len + 1;
      st[cl].link = st[q].link;
      memcpy(st[cl].next, st[q].next, sizeof(st[cl].next));
      for (; p != -1 && st[p].next[c] == q; p = st[p].link) st[p].next[c] = cl;
      st[now].link = st[q].link = cl;
    }
  }
  last = now;
}
vector<int> adj[1000005];
void dfs(long long int u) {
  for (auto p : adj[u]) {
    dfs(p);
    cost[u] += cost[p];
  }
}
void process() {
  long long int i, j, x = 0;
  for (i = 1; i <= siz; i++) {
    long long int p = st[i].link;
    adj[p].push_back(i);
  }
  dfs(0);
}
string t[500005];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long int n, i, j, x;
  siz = 0;
  memset(st, 0, sizeof(st));
  st[0].link = -1;
  while (cin >> n) {
    for (i = 1; i <= n; i++) cin >> t[i];
    for (i = 1; i <= n; i++) {
      cin >> x;
      for (auto p : t[i]) {
        inser(p - 'a', x);
      }
      last = 0;
    }
    process();
    long long int ans = 0;
    for (i = 1; i <= siz; i++) {
      long long int r = st[i].link;
      if (st[r].len >= st[i].len) continue;
      long long int p = st[i].len * cost[i];
      ans = max(ans, p);
    }
    cout << ans << endl;
  }
}