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 size_c = 26;
const int Maxn = 500010 << 1;
string s[100020];
int w[100020];
int n;
struct Suffix_Automaton {
  int ch[Maxn][size_c];
  int f[Maxn];
  int ml[Maxn];
  int sz, head, tail;
  long long val[Maxn];
  int cnt[Maxn], id[Maxn];
  inline int getidx(char c) { return c - 'a'; }
  int node() {
    sz++;
    f[sz] = ml[sz] = 0;
    memset(ch[sz], 0, sizeof(ch[sz]));
    return sz;
  }
  void init() {
    head = tail = 1;
    sz = 0;
    node();
  }
  void insert(int idx) {
    head = tail = 1;
    for (int i = 0; i < s[idx].size(); i++) add(getidx(s[idx][i]));
  }
  void add(int c) {
    int p = tail;
    if (ch[p][c]) {
      int q = ch[p][c];
      if (ml[q] == ml[p] + 1) {
        tail = ch[p][c];
      } else {
        int nq = node();
        memcpy(ch[nq], ch[q], sizeof(ch[q]));
        f[nq] = f[q];
        f[q] = nq;
        ml[nq] = ml[p] + 1;
        for (; p && ch[p][c] == q; p = f[p]) ch[p][c] = nq;
        tail = nq;
      }
      return;
    }
    int np = node();
    ml[np] = ml[p] + 1;
    tail = np;
    for (; p && !ch[p][c]; p = f[p]) ch[p][c] = np;
    if (!p)
      f[np] = head;
    else if (ml[ch[p][c]] == ml[p] + 1)
      f[np] = ch[p][c];
    else {
      int q = ch[p][c];
      int nq = node();
      memcpy(ch[nq], ch[q], sizeof(ch[q]));
      f[nq] = f[q];
      f[q] = f[np] = nq;
      ml[nq] = ml[p] + 1;
      for (; p && ch[p][c] == q; p = f[p]) ch[p][c] = nq;
    }
  }
  void solve() {
    init();
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> s[i];
    for (int i = 1; i <= n; i++) scanf("%d", w + i);
    for (int i = 1; i <= n; i++) insert(i);
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= sz; i++) cnt[ml[i]]++;
    for (int i = 1; i <= sz; i++) cnt[i] += cnt[i - 1];
    for (int i = 1; i <= sz; i++) id[cnt[ml[i]]--] = i;
    memset(cnt, 0, sizeof(cnt));
    for (int idx = 1; idx <= n; idx++) {
      int rt = 1;
      for (int i = 0; i < s[idx].size(); i++) {
        rt = ch[rt][getidx(s[idx][i])];
        val[rt] += w[idx];
      }
    }
    for (int i = sz; i >= 1; i--) {
      int cur = id[i];
      val[f[cur]] += val[cur];
    }
    long long ans = 0;
    for (int i = 1; i <= sz; i++) ans = max(ans, 1LL * ml[i] * val[i]);
    cout << ans << endl;
  }
} suf;
int main() { suf.solve(); }