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;
inline int read() {
  static char ch;
  bool sgn = false;
  while (ch = getchar(), ch < '0' || ch > '9')
    if (ch == '-') sgn = true;
  int res = ch - 48;
  while (ch = getchar(), ch >= '0' && ch <= '9') res = res * 10 + ch - 48;
  return sgn ? -res : res;
}
const int N = 1e6 + 3;
int l, n, k;
string s[N];
long long ans, cost[N];
bool cmp(int a, int b);
int tot, last;
struct SAM {
  int ch[N][26], dep[N], fa[N], a[N];
  long long r[N];
  void init() {
    tot = last = 1;
    memset(ch[1], 0, sizeof(ch[1]));
  }
  inline int newnode(int _dep) {
    dep[++tot] = _dep;
    memset(ch[tot], 0, sizeof(ch[tot]));
    return tot;
  }
  void add(int alp) {
    alp -= 'a';
    if (ch[last][alp]) {
      if (dep[ch[last][alp]] == dep[last] + 1)
        last = ch[last][alp];
      else {
        int u = last, v = ch[last][alp], nv = newnode(dep[last] + 1);
        fa[nv] = fa[v];
        fa[v] = nv;
        memcpy(ch[nv], ch[v], sizeof(ch[v]));
        for (; u && ch[u][alp] == v; u = fa[u]) ch[u][alp] = nv;
        last = nv;
      }
      return;
    }
    int u, p = newnode(dep[last] + 1);
    for (u = last; u && !ch[u][alp]; u = fa[u]) ch[u][alp] = p;
    if (!u)
      fa[p] = 1;
    else {
      int v = ch[u][alp];
      if (dep[v] == dep[u] + 1)
        fa[p] = v;
      else {
        int nv = newnode(dep[u] + 1);
        fa[nv] = fa[v];
        fa[v] = fa[p] = nv;
        memcpy(ch[nv], ch[v], sizeof(ch[v]));
        for (; u && ch[u][alp] == v; u = fa[u]) ch[u][alp] = nv;
      }
    }
    last = p;
  }
  void cal_r() {
    for (int j = 0; j < n; j++) {
      int now = 1;
      for (int i = 0; i < s[j].length(); i++) {
        now = ch[now][s[j][i] - 'a'];
        r[now] += cost[j];
      }
    }
    for (int i = 1; i <= tot; i++) a[i] = i;
    sort(a + 1, a + 1 + tot, cmp);
    for (int i = 1; i <= tot; i++) r[fa[a[i]]] += r[a[i]];
  }
  void solve() {
    cal_r();
    for (int i = 2; i <= tot; i++) ans = max(ans, r[i] * dep[i]);
  }
} S;
bool cmp(int a, int b) { return S.dep[a] > S.dep[b]; }
int main() {
  n = read();
  S.init();
  for (int j = 0; j < n; j++) {
    cin >> s[j];
    last = 1;
    for (int i = 0; i < s[j].length(); i++) S.add(s[j][i]);
  }
  for (int i = 0; i < n; i++) cost[i] = read();
  S.solve();
  cout << ans;
}