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 nsz = 1e5, msz = 5e5 + nsz, asz = 26 + nsz;
int n, m, a[nsz + 5], s[msz + 5], fm[msz + 5], len[msz + 5], l[msz + 5],
    r[msz + 5];
long long pre[msz + 5], ans;
char t[msz + 5];
struct suffix_array {
  int sz, as, sa[msz + 5], rk[msz + 5], id[msz + 5], h[msz + 5];
  int inline operator[](int id) { return sa[id]; }
  void inline radix_sort() {
    static int b[msz + 5], tmp[msz + 5];
    fill(b, b + as + 1, 0);
    for (int i = 0; i < sz; ++i) ++b[tmp[i] = rk[id[i]]];
    for (int i = 1; i <= as; ++i) b[i] += b[i - 1];
    for (int i = sz - 1; i >= 0; --i) sa[--b[tmp[i]]] = id[i];
  }
  void inline init(int sz, int s[]) {
    this->sz = sz, as = asz;
    for (int i = 0; i < sz; ++i) rk[i] = s[i], id[i] = i;
    radix_sort();
    for (int k = 1; k < sz; k <<= 1) {
      for (int i = 0; i < sz; ++i) id[i] = (sa[i] - k + sz) % sz;
      radix_sort();
      for (int i = 0; i < sz; ++i) id[i] = rk[i];
      as = 0;
      for (int i = 0; i < sz; ++i)
        rk[sa[i]] = (i && id[sa[i]] == id[sa[i - 1]] &&
                             id[(sa[i] + k) % sz] == id[(sa[i - 1] + k) % sz]
                         ? as
                         : ++as) -
                    1;
      if (as == sz) break;
    }
    for (int i = 0, k = 0; i < sz; ++i, k && --k) {
      for (; rk[i] && s[(i + k) % sz] == s[(sa[rk[i] - 1] + k) % sz]; ++k)
        ;
      h[rk[i]] = k;
    }
  }
};
suffix_array sa;
int main() {
  scanf("%d", &n);
  for (int id = 1; id <= n; ++id) {
    scanf("%s", t);
    int k = strlen(t);
    for (int i = 0; i < k; ++i) {
      fm[m] = id;
      len[m] = k - i;
      s[m++] = t[i] - 'a' + nsz + 1;
    }
    s[m++] = id;
  }
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
  }
  sa.init(m, s);
  pre[0] = a[fm[sa[0]]];
  for (int i = 1; i <= sa.sz - 1; ++i) {
    pre[i] = pre[i - 1] + a[fm[sa[i]]];
  }
  static int ss, stk[msz + 5];
  ss = 0;
  for (int i = 0; i < sa.sz; ++i) {
    for (; ss && sa.h[stk[ss - 1]] >= sa.h[i]; --ss)
      ;
    l[i] = ss ? stk[ss - 1] + 1 : 0;
    stk[ss++] = i;
  }
  ss = 0;
  for (int i = sa.sz - 1; i >= 0; --i) {
    for (; ss && sa.h[stk[ss - 1]] >= sa.h[i]; --ss)
      ;
    r[i] = ss ? stk[ss - 1] - 1 : sa.sz - 1;
    stk[ss++] = i;
  }
  for (int i = 0; i < sa.sz; ++i) {
    long long sum = pre[r[i]] - (l[i] - 2 >= 0 ? pre[l[i] - 2] : 0);
    ans = max(ans, sum * sa.h[i]);
  }
  for (int i = 0; i < sa.sz; ++i) {
    if (sa.h[sa.rk[i]] >= len[i] || sa.h[sa.rk[i] + 1] >= len[i]) continue;
    ans = max(ans, (long long)len[i] * a[fm[i]]);
  }
  printf("%lld\n", ans);
}