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 maxn = 5e5 + 10;
int n, hed[maxn], nxt[maxn], pre[maxn], id[maxn], c[maxn], a[maxn], lcp[maxn],
    hel[maxn], part[maxn], new_id[maxn];
string second, s[maxn];
vector<int> add[maxn];
long long Ans, pc[maxn];
void round_1() {
  cin >> n;
  second = "#";
  for (int y = 1; y <= n; y++) cin >> s[y];
  int tmp = 1;
  int hel;
  for (int y = 1; y <= n; y++) {
    cin >> hel;
    second += s[y];
    for (int x = tmp; x < 1LL * second.size(); x++)
      id[x] = second[x] - 'a' + 1, hed[x] = 1LL * second.size() - 1, c[x] = hel,
      nxt[x] = pre[x] = x;
    tmp = 1LL * second.size();
  }
  n = 1LL * second.size() - 1;
}
void SuffixArray() {
  for (int _ = 0; n >> _; _++) {
    memset(part, 0, sizeof part);
    for (int y = 1; y <= n; y++) {
      int z = y + (1 << _) <= hed[y] ? id[y + (1 << _)] : 0;
      part[z + 1]++;
    }
    for (int y = 1; y <= max(n, 30); y++) part[y] += part[y - 1];
    for (int y = 1; y <= n; y++) {
      int z = y + (1 << _) <= hed[y] ? id[y + (1 << _)] : 0;
      hel[++part[z]] = y;
    }
    memset(part, 0, sizeof part);
    for (int y = 1; y <= n; y++) part[id[y] + 1]++;
    for (int y = 1; y <= max(n, 30); y++) part[y] += part[y - 1];
    for (int y = 1; y <= n; y++) a[++part[id[hel[y]]]] = hel[y];
    new_id[a[1]] = 1;
    for (int y = 2; y <= n; y++) {
      int z1 =
          a[y - 1] + (1 << _) <= hed[a[y - 1]] ? id[a[y - 1] + (1 << _)] : 0;
      int z2 = a[y] + (1 << _) <= hed[a[y]] ? id[a[y] + (1 << _)] : 0;
      new_id[a[y]] = new_id[a[y - 1]] + !(id[a[y]] == id[a[y - 1]] && z1 == z2);
    }
    for (int y = 1; y <= n; y++) id[y] = new_id[y];
  }
  int cur = 1;
  for (int y = 1; y <= n; y++) pc[y] = pc[y - 1] + c[a[y]];
  for (int y = 2; y <= n + 1; y++) {
    if (y == n + 1 || id[a[y]] != id[a[y - 1]]) {
      Ans = max(Ans, (pc[y - 1] - pc[cur - 1]) * (hed[a[cur]] - a[cur] + 1));
      cur = y;
    }
  }
  cur = 0;
  for (int y = 1; y <= n; y++) id[a[y]] = y;
  for (int y = 1; y <= n; y++) {
    cur = max(0, cur - 1);
    int i = id[y];
    while (cur + a[i] <= hed[a[i]] && cur + a[i + 1] <= hed[a[i + 1]] &&
           second[a[i] + cur] == second[a[i + 1] + cur])
      cur++;
    lcp[i] = min(cur, min(hed[a[i]] - a[i], hed[a[i + 1]] - a[i + 1]) + 1);
    add[lcp[i]].push_back(i);
  }
}
void EndGame() {
  for (int y = n; y; y--) {
    for (auto A : add[y]) nxt[pre[A]] = nxt[A + 1], pre[nxt[A + 1]] = pre[A];
    for (auto A : add[y]) {
      int i = pre[A];
      int j = nxt[i];
      if (pre[j] == i) Ans = max(Ans, 1LL * (pc[j] - pc[i - 1]) * y);
    }
  }
  cout << Ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  round_1();
  SuffixArray();
  EndGame();
}