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 A = 30;
const int N = 6e5;
char s[N + 7];
int poz[2 * N + 7];
int len[2 * N + 7];
int h[2 * N + 7];
int T[2 * N + 7][A];
int suf[2 * N + 7];
int gid = 1;
int ov;
int n;
int L;
long long dp[2 * N + 7];
int cost[N + 7];
int gd[N + 7];
int ssu[N + 7];
long long wynik = 0;
inline int ile(int a, int b) { return ssu[b] - ssu[a - 1]; }
pair<int, int> fastscan(int v, int a, int l) {
  while (1) {
    if (l == 0) return {v, 0};
    int w = T[v][s[a] - 'a'];
    if (l < len[w]) return {v, l};
    l -= len[w];
    a += len[w];
    v = w;
  }
}
void dfs1(int v) {
  for (int i = 0; i < A; ++i) {
    if (T[v][i]) {
      dfs1(T[v][i]);
      dp[v] += dp[T[v][i]];
    }
  }
}
void dfs2(int v, int l) {
  for (int i = 0; i < A; ++i) {
    int w = T[v][i];
    if (w) {
      int a = poz[w];
      int b = poz[w] + len[w] - 1;
      if (ile(a, b) == 0) {
        wynik = max(wynik, dp[w] * (l + len[w]));
        dfs2(w, l + len[w]);
      } else {
        int p = a;
        int k = b;
        b = a - 1;
        while (p <= k) {
          int s = (p + k) / 2;
          if (ile(a, s) == 0) {
            b = s;
            p = s + 1;
          } else
            k = s - 1;
        }
        wynik = max(wynik, dp[w] * (l + b - a + 1));
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> (s + L + 1);
    while (s[L + 1]) {
      L++;
      gd[L] = i;
    }
    s[++L] = 'z' + 1;
    ssu[L] = 1;
  }
  for (int i = 1; i <= n; ++i) cin >> cost[i];
  s[++L] = 'z' + 2;
  int j = 1;
  int v = 1;
  suf[1] = 1;
  for (int i = 1; i <= L; ++i) ssu[i] += ssu[i - 1];
  for (int i = 1; i <= L; ++i) {
    while (j <= i) {
      pair<int, int> r = fastscan(v, j + h[v], i - j - h[v]);
      v = r.first;
      int u = v;
      suf[ov] = v;
      if (r.second == 0) ov = 0;
      int w = T[v][s[j + h[v]] - 'a'];
      if (w && s[poz[w] + r.second] == s[i]) break;
      if (r.second) {
        ++gid;
        len[gid] = r.second;
        len[w] -= r.second;
        h[gid] = h[v] + r.second;
        poz[gid] = poz[w];
        poz[w] += r.second;
        T[v][s[j + h[v]] - 'a'] = gid;
        T[gid][s[poz[w]] - 'a'] = w;
        v = gid;
        suf[ov] = gid;
        ov = gid;
      }
      ++gid;
      h[gid] = L - j + 1;
      len[gid] = h[gid] - h[v];
      poz[gid] = i;
      T[v][s[j + h[v]] - 'a'] = gid;
      dp[gid] = cost[gd[j]];
      j++;
      v = suf[u];
    }
  }
  dfs1(1);
  dfs2(1, 0);
  cout << wynik << endl;
  return 0;
}