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;
int n, d;
long long ans;
string t[600007];
int s[600007];
int c[600007];
int pos[600007];
int lcp[600007];
long long pref_cost[600007];
int cost[600007];
int lewo[600007];
int prawo[600007];
int dlugosc[600007];
pair<int, int> cmp[600007];
vector<int> sa;
bool comp(int a, int b) { return cmp[a] < cmp[b]; }
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> t[i];
  }
  for (int i = 1; i <= n; ++i) {
    cin >> c[i];
  }
  for (int i = 1; i <= n; ++i) {
    s[++d] = 256 + d;
    for (int j = 0; j < t[i].size(); ++j) {
      s[++d] = t[i][j];
      dlugosc[d] = t[i].size() - j;
      cost[d] = c[i];
    }
  }
  for (int i = 1; i <= d; ++i) {
    sa.push_back(i);
    cmp[i] = make_pair(s[i], -1);
  }
  for (int l = 1; l <= 2 * d; l *= 2) {
    sort((sa).begin(), (sa).end(), comp);
    for (int i = 0; i < d; ++i) {
      if (i > 0 && cmp[sa[i - 1]] == cmp[sa[i]])
        pos[sa[i]] = pos[sa[i - 1]];
      else
        pos[sa[i]] = i;
    }
    for (int i = 1; i <= d; ++i) {
      if (i + l <= d)
        cmp[i] = make_pair(pos[i], pos[i + l]);
      else
        cmp[i] = make_pair(pos[i], -1);
    }
  }
  int curr = 0;
  for (int i = 1; i <= d; ++i) {
    if (pos[i] == d - 1) {
      curr = max(--curr, 0);
      continue;
    }
    while (i + curr <= d && sa[pos[i] + 1] + curr <= d &&
           s[i + curr] == s[sa[pos[i] + 1] + curr])
      ++curr;
    lcp[pos[i]] = curr;
    curr = max(--curr, 0);
  }
  for (int i = 0; i < d; ++i) {
    pref_cost[i] += cost[sa[i]];
    pref_cost[i + 1] += pref_cost[i];
  }
  lewo[0] = -1;
  for (int i = 1; i < d; ++i) {
    int j = i - 1;
    while (j != -1 && lcp[j] >= lcp[i]) j = lewo[j];
    lewo[i] = j;
  }
  prawo[d - 1] = d;
  for (int i = d - 2; i >= 0; --i) {
    int j = i + 1;
    while (j != d && lcp[j] >= lcp[i]) j = prawo[j];
    prawo[i] = j;
  }
  for (int i = 0; i < d - 1; ++i) {
    int l = lewo[i] + 1;
    int r = prawo[i];
    if (r < d)
      ans = max(ans, (long long)lcp[i] *
                         (pref_cost[r] - (l == 0 ? 0 : pref_cost[l - 1])));
    if (lcp[i] < dlugosc[sa[i]] && (i == 0 || lcp[i - 1] < dlugosc[sa[i]]))
      ans = max(ans, (long long)dlugosc[sa[i]] * cost[sa[i]]);
  }
  cout << ans;
}