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 N = 1.12e5;
const int LEN = 6.4 * N;
int len;
int c[N], sz[N];
int s[LEN], sa[LEN], *rk, ht[LEN], v[2][LEN], ct[LEN], cost[LEN];
long long co[LEN];
void build_sa(int n, int m) {
  int *x = v[0], *y = v[1];
  fill_n(ct, m, 0);
  for (int i = (0); i != (n); ++i) ++ct[x[i] = s[i]];
  for (int i = (1); i != (m); ++i) ct[i] += ct[i - 1];
  for (int i = (n - 1); i != (-1); --i) sa[--ct[x[i]]] = i;
  for (int k = 1; k < n; k <<= 1) {
    int p = 0;
    for (int i = (n - k); i != (n); ++i) y[p++] = i;
    for (int i = (0); i != (n); ++i)
      if (sa[i] >= k) y[p++] = sa[i] - k;
    fill_n(ct, m, 0);
    for (int i = (0); i != (n); ++i) ++ct[x[y[i]]];
    for (int i = (1); i != (n); ++i) ct[i] += ct[i - 1];
    for (int i = (n - 1); i != (-1); --i) sa[--ct[x[y[i]]]] = y[i];
    swap(x, y);
    x[sa[0]] = 0;
    p = 1;
    for (int i = (1); i != (n); ++i)
      x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]
                     ? p - 1
                     : p++;
    if ((m = p) == n) {
      rk = x;
      break;
    }
  }
  int h = 0;
  ht[0] = 0;
  for (int i = (0); i != (n); ++i) {
    if (!rk[i]) {
      h = 0;
      continue;
    }
    while (s[i + h] == s[sa[rk[i] - 1] + h]) ++h;
    ht[rk[i]] = h;
    if (h) --h;
  }
}
int ls[LEN], rs[LEN];
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
typedef int (*func)(int, int);
struct BIT {
  func f;
  int t[LEN], v;
  void init(func _f, int _v) {
    f = _f;
    v = _v;
    fill_n(t, len + 1, v);
  }
  void add(int i, int x) {
    for (; i <= len; i += i & -i) t[i] = f(t[i], x);
  }
  int qry(int i) {
    int ret = v;
    for (; i; i ^= i & -i) ret = f(ret, t[i]);
    return ret;
  }
} bit;
int main() {
  int n;
  scanf("%d ", &n);
  len = 0;
  for (int i = (0); i != (n); ++i) {
    int ch;
    int la = len;
    while ((ch = getchar()) != '\n') s[len++] = n + ch - 'a';
    sz[i] = len - la;
    s[len++] = i;
  }
  long long ans = 0;
  for (int i = (0); i != (n); ++i) scanf("%d", c + i);
  build_sa(len, n + 26);
  int la = 0;
  for (int i = (0); i != (n); ++i) {
    if (ht[rk[la]] != sz[i] && ht[rk[la] + 1] != sz[i])
      ans = max(ans, sz[i] * 1LL * c[i]);
    la += sz[i] + 1;
  }
  int idx = n - 1;
  for (int i = (len - 1); i != (-1); --i) cost[i] = c[idx = min(idx, s[i])];
  for (int i = (0); i != (len); ++i) co[i] = cost[sa[i]];
  for (int i = (1); i != (len); ++i) co[i] += co[i - 1];
  bit.init(max, -1);
  for (int i = (0); i != (len); ++i) {
    ls[i] = bit.qry(ht[i]);
    bit.add(ht[i] + 1, i);
  }
  bit.init(min, len);
  for (int i = (len - 1); i != (-1); --i) {
    rs[i] = bit.qry(ht[i]);
    bit.add(ht[i] + 1, i);
  }
  for (int i = (0); i != (len); ++i)
    if (ht[i]) ans = max(ans, ht[i] * (co[rs[i] - 1] - co[ls[i] - 1]));
  printf("%lld\n", ans);
}