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;
template <class T>
inline void input(T &x) {
  register char c = getchar();
  x = 0;
  int neg = 0;
  for (; ((c < 48 || c > 57) && c != '-'); c = getchar())
    ;
  if (c == '-') {
    neg = 1;
    c = getchar();
  }
  for (; c > 47 && c < 58; c = getchar()) {
    x = (x << 1) + (x << 3) + c - 48;
  }
  if (neg) x = -x;
}
inline long long bigmod(long long p, long long e, long long M) {
  long long ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T modinverse(T a, T M) {
  return bigmod(a, M - 2, M);
}
using namespace std;
const int maxn = 1e6 + 5;
int wa[maxn], wb[maxn], wv[maxn], wc[maxn];
int r[maxn], sa[maxn], rak[maxn], height[maxn], dp[maxn][22], jump[maxn],
    SIGMA = 1e5 + 30;
int cmp(int *r, int a, int b, int l) {
  return r[a] == r[b] && r[a + l] == r[b + l];
}
void da(int *r, int *sa, int n, int m) {
  int i, j, p, *x = wa, *y = wb, *t;
  for (i = 0; i < m; i++) wc[i] = 0;
  for (i = 0; i < n; i++) wc[x[i] = r[i]]++;
  for (i = 1; i < m; i++) wc[i] += wc[i - 1];
  for (i = n - 1; i >= 0; i--) sa[--wc[x[i]]] = i;
  for (j = 1, p = 1; p < n; j *= 2, m = p) {
    for (p = 0, i = n - j; i < n; i++) y[p++] = i;
    for (i = 0; i < n; i++)
      if (sa[i] >= j) y[p++] = sa[i] - j;
    for (i = 0; i < n; i++) wv[i] = x[y[i]];
    for (i = 0; i < m; i++) wc[i] = 0;
    for (i = 0; i < n; i++) wc[wv[i]]++;
    for (i = 1; i < m; i++) wc[i] += wc[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--wc[wv[i]]] = y[i];
    for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++)
      x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
  }
}
void calheight(int *r, int *sa, int n) {
  int i, j, k = 0;
  for (i = 1; i <= n; i++) rak[sa[i]] = i;
  for (i = 0; i < n; height[rak[i++]] = k) {
    for (k ? k-- : 0, j = sa[rak[i] - 1]; r[i + k] == r[j + k]; k++)
      ;
  }
}
void initRMQ(int n) {
  for (int i = 0; i <= n; i++) dp[i][0] = height[i];
  for (int j = 1; (1 << j) <= n; j++) {
    for (int i = 0; i + (1 << j) - 1 <= n; i++) {
      dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
    }
  }
  for (int i = 1; i <= n; i++) {
    int k = 0;
    while ((1 << (k + 1)) <= i) k++;
    jump[i] = k;
  }
}
int askRMQ(int L, int R) {
  int k = jump[R - L + 1];
  return min(dp[L][k], dp[R - (1 << k) + 1][k]);
}
const int N = 1e6 + 6;
char str[N];
int n = 0;
int c[N], value[N], len[N], rest[N];
long long pr[N], Id[N];
long long sum(int a, int b) { return pr[b] - pr[a - 1]; }
int main() {
  int t = 0, dummy = 28;
  input(t);
  n = 0;
  long long ans = 0;
  for (int i = 1; i <= t; i++) {
    scanf(" %s ", str);
    len[i] = strlen(str);
    int pos = len[i];
    for (int j = 0; str[j]; j++)
      r[n] = str[j] - 'a' + 1, Id[n] = i, rest[n] = pos--, n++;
    r[n++] = dummy++;
  }
  r[n] = 0;
  da(r, sa, n + 1, SIGMA + 1);
  calheight(r, sa, n);
  initRMQ(n);
  for (int i = 1; i <= t; i++) {
    input(c[i]);
  }
  for (int i = 0; i <= n; i++) {
    if (Id[sa[i]] > 0) value[i] = c[Id[sa[i]]];
  }
  for (int i = 0; i <= n; i++) {
    pr[i] = value[i] + (i > 0 ? pr[i - 1] : 0);
  }
  for (int i = 1; i <= n; i++) {
    int v = height[i];
    if (v < rest[sa[i]] && height[i + 1] < rest[sa[i]])
      ans = max(ans, 1LL * rest[sa[i]] * c[Id[sa[i]]]);
    if (v == 0) continue;
    int L = i - 1, R = i;
    int low = 0, high = i - 1, mid;
    while (low <= high) {
      mid = (low + high) / 2;
      if (askRMQ(mid + 1, i) >= v) {
        L = mid;
        high = mid - 1;
      } else
        low = mid + 1;
    }
    low = i, high = n;
    while (low <= high) {
      mid = (low + high) / 2;
      if (askRMQ(i + 1, mid) >= v) {
        R = mid;
        low = mid + 1;
      } else
        high = mid - 1;
    }
    ans = max(ans, 1LL * sum(L, R) * v);
  }
  cout << ans << endl;
  return 0;
}