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 nsz = 1e5, ndsz = 2 * 5e5, asz = 26;
int n, a[nsz + 5];
int es, hd[ndsz + 5];
long long ans, sum[ndsz + 5];
string s[nsz + 5];
struct suffix_automaton {
  int rt, sz, lst, lnk[ndsz + 5], len[ndsz + 5], g[ndsz + 5][26];
  suffix_automaton() { rt = ++sz; }
  void inline ins(char ch) {
    int c = ch - 'a', p = lst, u = lst = ++sz;
    len[u] = len[p] + 1;
    for (; p && !g[p][c]; g[p][c] = u, p = lnk[p])
      ;
    if (!p) {
      lnk[u] = rt;
      return;
    }
    int q = g[p][c];
    if (len[q] == len[p] + 1) {
      lnk[u] = q;
    } else {
      int v = ++sz;
      len[v] = len[p] + 1, lnk[v] = lnk[q];
      for (int c = 0; c < 26; ++c) {
        g[v][c] = g[q][c];
      }
      for (; p && g[p][c] == q; g[p][c] = v, p = lnk[p])
        ;
      lnk[u] = lnk[q] = v;
    }
  }
  void inline ins(string s) {
    lst = 1;
    for (int i = 0; i < s.size(); ++i) {
      ins(s[i]);
    }
  }
};
suffix_automaton sam;
struct edge {
  int nxt, to;
  edge(int nxt = 0, int to = 0) { this->nxt = nxt, this->to = to; }
};
edge e[ndsz + 5];
void inline link(int u, int v) { e[++es] = edge(hd[u], v), hd[u] = es; }
void inline upd(string s, int w) {
  int u = sam.rt;
  for (int i = 0; i < s.size(); ++i) {
    u = sam.g[u][s[i] - 'a'];
    sum[u] += w;
  }
}
void dfs(int u = sam.rt) {
  for (int i = hd[u]; i; i = e[i].nxt) {
    int v = e[i].to;
    dfs(v);
    sum[u] += sum[v];
  }
  ans = max(ans, sum[u] * sam.len[u]);
}
int main() {
  ios::sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> s[i];
    sam.ins(s[i]);
  }
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    upd(s[i], a[i]);
  }
  for (int i = 1; i <= sam.sz; ++i) {
    link(sam.lnk[i], i);
  }
  dfs();
  cout << ans << '\n';
}