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>
const int MAXN = 1000006;
using namespace std;
int n, m, w, sz, klas;
char s[MAXN], t[MAXN];
long long cost[MAXN], ln[MAXN], ans, len;
int p[MAXN], pn[MAXN], c[MAXN], cn[MAXN], val[MAXN], S[MAXN];
int cnt[MAXN], rnk[MAXN], lcp[MAXN], L[MAXN], R[MAXN], st[MAXN];
void suffix_array() {
  for (int i = 0; i < n; i++) cnt[(int)s[i]]++;
  for (int i = 1; i < 256; i++) cnt[i] += cnt[i - 1];
  for (int i = 0; i < n; i++) p[--cnt[(int)s[i]]] = i;
  for (int i = 1; i < n; i++) c[p[i]] = klas += (s[p[i]] != s[p[i - 1]]);
  for (int j = 0; (1 << j) < n; j++) {
    memset(cnt, 0, (klas + 1) * sizeof(int));
    for (int i = 0; i < n; i++) pn[i] = (p[i] - (1 << j) + n) % n;
    for (int i = 0; i < n; i++) cnt[c[pn[i]]]++;
    for (int i = 1; i <= klas; i++) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; i--) p[--cnt[c[pn[i]]]] = pn[i];
    cn[p[0]] = klas = 0;
    for (int i = 1; i < n; i++)
      cn[p[i]] = klas +=
          (c[p[i]] != c[p[i - 1]] ||
           c[(p[i] + (1 << j)) % n] != c[(p[i - 1] + (1 << j)) % n]);
    memcpy(c, cn, n * sizeof(int));
  }
}
void lcp_table() {
  for (int i = 0; i < n; i++) rnk[p[i]] = i;
  for (int i = 0, k = 0; i < n; i++, k ? k-- : 0) {
    if (rnk[i] == n - 1) {
      k = 0;
      continue;
    }
    int j = p[rnk[i] + 1];
    while (s[i + k] != '#' && s[j + k] != '#' && s[i + k] == s[j + k]) k++;
    lcp[rnk[i]] = k;
  }
}
int main() {
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    scanf("%s", t);
    st[n] = 1;
    for (len = 0; t[len] != '\0'; len++) s[n++] = t[len];
    for (int h = n - 1; h >= n - len; h--) ln[h] = len;
    s[n++] = '#';
  }
  for (int i = 0, j = -1; i < m; i++) {
    scanf("%d", &w);
    while (++j < n && s[j] != '#') val[j] = w;
  }
  suffix_array();
  lcp_table();
  for (int i = 0; i < n; i++) {
    R[i] = n;
    while (sz > 0 && lcp[S[sz - 1]] >= lcp[i]) R[S[--sz]] = i;
    if (sz > 0) L[i] = S[sz - 1] + 1;
    S[sz++] = i;
  }
  for (int i = 0; i < n; i++) cost[rnk[i]] = val[i];
  for (int i = 1; i < n; i++) cost[i] += cost[i - 1];
  for (int i = 0; i < n; i++) {
    if (st[p[i]] && lcp[i] < ln[p[i]] && lcp[i + 1] < ln[p[i]] &&
        ln[p[i]] != lcp[i - 1])
      ans = max(ans, ln[p[i]] * val[p[i]]);
    if ((!L[i] || lcp[L[i] - 1] < lcp[i]) && lcp[R[i]] < lcp[i])
      ans = max(ans, (cost[R[i]] - (L[i] ? cost[L[i] - 1] : 0)) * lcp[i]);
  }
  printf("%lld", ans);
}