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>
struct state {
  int link, len, ml;
  std::map<int, int> to;
  long long cost;
  state() {
    link = -1;
    len = cost = ml = 0;
  };
};
const int N = 100000;
const int L = 500000;
const int A = 26;
int n, size = 1, l[N];
char s[N + L];
state sa[(N + L) * 2 - 1];
std::pair<int, int> st[(N + L) * 2 - 1];
void add(int c, int k, int ml) {
  static int last = 0;
  sa[size].len = sa[last].len + 1;
  sa[size].cost = k;
  sa[size].ml = ml;
  int cur = last;
  last = size++;
  do {
    sa[cur].to.insert(std::make_pair(c, last));
    cur = sa[cur].link;
  } while (cur != -1 && !sa[cur].to.count(c));
  if (cur == -1)
    sa[last].link = 0;
  else {
    int t = sa[cur].to[c];
    if (sa[t].len == sa[cur].len + 1)
      sa[last].link = t;
    else {
      sa[size] = sa[t];
      sa[t].link = sa[last].link = size;
      sa[size].len = sa[size].ml = sa[cur].len + 1;
      sa[size].cost = 0;
      do {
        sa[cur].to[c] = size;
        cur = sa[cur].link;
      } while (cur != -1 && sa[cur].to.count(c) && sa[cur].to[c] == t);
      ++size;
    }
  }
}
int main() {
  scanf("%d", &n);
  char *p = s;
  for (int i = 0; i < n; ++i) {
    scanf("%s", p);
    l[i] = strlen(p);
    p += l[i];
  }
  p = s;
  for (int i = 0; i < n; ++i) {
    int c;
    scanf("%d", &c);
    add(A + i, 0, 0);
    for (int j = 0; j < l[i]; ++j, ++p) add(*p - 'a', c, j + 1);
  }
  for (int i = 0; i < size; ++i) st[i] = std::make_pair(sa[i].len, i);
  std::sort(st, st + size);
  for (int i = size - 1; i > 0; --i)
    sa[sa[st[i].second].link].cost += sa[st[i].second].cost;
  long long ans = 0;
  for (int i = 1; i < size; ++i)
    if (sa[i].ml == sa[i].len || sa[sa[i].link].len != sa[i].ml)
      ans = std::max(ans, sa[i].cost * sa[i].ml);
  printf("%lld\n", ans);
  return 0;
}