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 double PI = acos(0) * 2;
const double EPS = 1e-8;
const long long MOD = 1e9 + 7;
const int MAXN = 6e5 + 5;
const int oo = 1e9;
const double foo = 1e30;
template <class T>
int getbit(T s, int i) {
  return (s >> i) & 1;
}
template <class T>
T onbit(T s, int i) {
  return s | (T(1) << i);
}
template <class T>
T offbit(T s, int i) {
  return s & (~(T(1) << i));
}
template <class T>
int cntbit(T s) {
  return __builtin_popcounll(s);
}
template <class T>
T sqr(T x) {
  return x * x;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
struct SuffixArray {
  static const int MAXN = 6e5 + 5;
  static const char SEP = '$';
  string T;
  int n;
  int RA[MAXN], tmpRA[MAXN];
  int SA[MAXN], tmpSA[MAXN];
  int c[MAXN];
  int Phi[MAXN], PLCP[MAXN];
  int LCP[MAXN];
  void build(string t) {
    T = t;
    n = T.size();
    for (int i = 0; i < n; i++) {
      RA[i] = tmpRA[i] = 0;
      SA[i] = tmpSA[i] = 0;
      Phi[i] = PLCP[i] = LCP[i] = 0;
    }
    constructSA();
    computeLCP();
  }
  void countingsort(int k) {
    int sum = 0, maxi = max(300, n);
    memset(c, 0, sizeof(c));
    for (int i = 0; i < n; i++) c[i + k < n ? RA[i + k] : 0]++;
    for (int i = 0; i < maxi; i++) {
      int t = c[i];
      c[i] = sum;
      sum += t;
    }
    for (int i = 0; i < n; i++)
      tmpSA[c[SA[i] + k < n ? RA[SA[i] + k] : 0]++] = SA[i];
    for (int i = 0; i < n; i++) SA[i] = tmpSA[i];
  }
  void constructSA() {
    int r;
    for (int i = 0; i < n; i++) RA[i] = T[i];
    for (int i = 0; i < n; i++) SA[i] = i;
    for (int k = 1; k < n; k <<= 1) {
      countingsort(k);
      countingsort(0);
      tmpSA[SA[0]] = r = 0;
      for (int i = 1; i < n; i++)
        tmpRA[SA[i]] =
            (RA[SA[i]] == RA[SA[i - 1]] && RA[SA[i] + k] == RA[SA[i - 1] + k])
                ? r
                : ++r;
      for (int i = 0; i < n; i++) RA[i] = tmpRA[i];
      if (RA[SA[n - 1]] == n - 1) break;
    }
  }
  void computeLCP() {
    int L = 0;
    Phi[SA[0]] = -1;
    for (int i = 1; i < n; i++) Phi[SA[i]] = SA[i - 1];
    for (int i = 0; i < n; i++) {
      if (!~Phi[i]) {
        PLCP[i] = 0;
        continue;
      }
      while (T[i + L] == T[Phi[i] + L] && T[i + L] != SEP) L++;
      PLCP[i] = L;
      L = max(L - 1, 0);
    }
    for (int i = 0; i < n; i++) LCP[i] = PLCP[SA[i]];
  }
} sa;
const int MAXLOG = 21;
int M[MAXN][MAXLOG], n, pos[MAXN];
string s[MAXN];
long long c[MAXN], val[MAXN], ans;
map<string, int> mm;
int getMin(int u, int v) {
  int k = log2(v - u + 1);
  return min(M[u][k], M[v - (1 << k) + 1][k]);
}
int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    mm[s[i]]++;
  }
  for (int i = 0; i < n; i++) {
    cin >> c[i];
    if (mm[s[i]] == 1) ans = max(ans, (long long)((int)(s[i]).size()) * c[i]);
  }
  string S = "";
  for (int i = 0; i < n; i++) {
    for (int j = ((int)(S).size());
         j < ((int)(S).size()) + ((int)(s[i]).size()); j++)
      pos[j] = i;
    pos[((int)(S).size()) + ((int)(s[i]).size())] = -1;
    S += s[i];
    S += "$";
  }
  sa.build(S);
  for (int i = 0; i < sa.n; i++) {
    if (~pos[sa.SA[i]]) val[i] = c[pos[sa.SA[i]]];
  }
  for (int i = 1; i < sa.n; i++) {
    val[i] = val[i - 1] + val[i];
  }
  for (int i = 0; i < sa.n; i++) {
    M[i][0] = sa.LCP[i];
  }
  for (int k = 1; (1 << k) <= sa.n; k++) {
    for (int i = 0; i + (1 << k) - 1 < sa.n; i++) {
      M[i][k] = min(M[i][k - 1], M[i + (1 << (k - 1))][k - 1]);
    }
  }
  for (int i = 0; i < sa.n; i++) {
    int l = 0, r = i - 1, findL = i, findR = i;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (getMin(mid, i) < sa.LCP[i]) {
        l = mid + 1;
      } else {
        r = mid - 1;
        findL = mid;
      }
    }
    findL--;
    l = i + 1, r = sa.n - 1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (getMin(i + 1, mid) < sa.LCP[i]) {
        r = mid - 1;
      } else {
        l = mid + 1;
        findR = mid;
      }
    }
    long long cur = val[findR] - (findL ? val[findL - 1] : 0);
    cur *= (long long)sa.LCP[i];
    ans = max(ans, cur);
  }
  cout << ans;
}