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;
int n, len;
char t[600013];
int id[600013];
int e[100013], c[100013];
pair<pair<int, int>, int> cur[600013];
int last[600013], where[600013];
int suffix[600013], lcp[600013];
void makeSA() {
  for (int i = 0; i < len; i++) {
    last[i] = t[i];
    cur[i].second = where[i] = i;
  }
  for (int k = 1; k < len; k *= 2) {
    for (int i = 0; i < len; i++) {
      cur[i].first = make_pair(last[i], 0);
      if (cur[i].second + k < len)
        cur[i].first.second = last[where[cur[i].second + k]];
    }
    sort(cur, cur + len);
    for (int i = 0; i < len; i++) where[cur[i].second] = i;
    last[0] = 0;
    for (int i = 1; i < len; i++)
      last[i] = last[i - 1] + (cur[i].first != cur[i - 1].first);
  }
  for (int i = 0; i < len; i++) suffix[i] = cur[i].second;
  int prev = 0;
  for (int i = 0; i < len; i++) {
    int& l = lcp[where[i]];
    l = max(0, prev - 1);
    while (t[i + l] == t[suffix[where[i] + 1] + l] && t[i + l] != '$') l += 1;
    lcp[where[i]] = l;
    prev = l;
  }
  lcp[len - 1] = 0;
}
long long sums[600013];
int l[600013], r[600013];
stack<int> has;
long long sum(int a, int b) { return sums[b] - (a ? sums[a - 1] : 0); }
void solve() {
  sums[0] = c[id[suffix[0]]];
  for (int i = 1; i < len; i++) sums[i] = sums[i - 1] + c[id[suffix[i]]];
  fill(l, l + len, -1);
  for (int i = 0; i < len - 1; i++) {
    while (has.size() && lcp[has.top()] >= lcp[i]) has.pop();
    if (has.size()) l[i] = has.top();
    has.push(i);
  }
  while (has.size()) has.pop();
  fill(r, r + len, len - 1);
  for (int i = len - 2; i >= 0; i--) {
    while (has.size() && lcp[has.top()] >= lcp[i]) has.pop();
    if (has.size()) r[i] = has.top();
    has.push(i);
  }
  long long ans = 0;
  for (int i = 0; i < len; i++) {
    if (t[suffix[i]] == '$') continue;
    if (i < len - 1)
      ans = max(ans, lcp[i] * (sums[r[i]] - (l[i] + 1 ? sums[l[i]] : 0)));
    long long dist = e[id[suffix[i]]] - suffix[i];
    if (i && dist == lcp[i - 1]) continue;
    if (dist == lcp[i]) continue;
    ans = max(ans, dist * c[id[suffix[i]]]);
  }
  printf("%lld\n", ans);
}
int main() {
  scanf("%d", &n);
  char* head = t;
  for (int i = 0; i < n; i++) {
    scanf(" %s", head);
    while (*head) {
      id[head - t] = i;
      head++;
    }
    e[i] = head - t;
    *head = '$';
    id[head - t] = n;
    head++;
  }
  len = head - t;
  for (int i = 0; i < n; i++) scanf("%d", &c[i]);
  makeSA();
  solve();
  return 0;
}