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 mult(int x, int y) {
  long long int ans, x1 = (long long int)x, y1 = (long long int)y;
  ans = (x1 * y1) % 1000000007;
  return (int)ans;
}
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int lcm(int a, int b) { return a * (b / gcd(a, b)); }
long long int pow1(long long int a, long long int b) {
  long long int ans = 1;
  while (b > 0) {
    if (b & 1) ans = (ans * a) % 1000000007;
    a = (a * a) % 1000000007;
    b >>= 1;
  }
  return ans;
}
const int inf = 1e9, N = 2e6 + 10, dollar = 257;
map<int, int> to[N];
int s[N];
int len[N] = {inf}, fps[N], link[N], suff[N], par[N], dollr[N], idx[N];
long long int sum[N], ans;
int node, pos, sz = 1, n = 0, cost[N], remain, cnt = 0;
int make_node(int _pos, int _len, int _par) {
  fps[sz] = _pos;
  len[sz] = _len;
  suff[sz] = n - remain;
  par[sz] = _par;
  return sz++;
}
void go_edge() {
  while (pos > len[to[node][s[n - pos]]]) {
    node = to[node][s[n - pos]];
    pos -= len[node];
  }
}
void add_letter(int c) {
  s[n++] = c;
  pos++;
  remain++;
  int last = 0;
  while (pos > 0) {
    go_edge();
    int edge = s[n - pos];
    int &v = to[node][edge];
    int t = s[fps[v] + pos - 1];
    if (v == 0) {
      v = make_node(n - pos, inf, node);
      link[last] = node;
      last = 0;
    } else if (t == c) {
      link[last] = node;
      return;
    } else {
      int u = make_node(fps[v], pos - 1, node);
      to[u][c] = make_node(n - 1, inf, u);
      to[u][t] = v;
      par[v] = u;
      fps[v] += pos - 1;
      len[v] -= pos - 1;
      v = u;
      link[last] = u;
      last = u;
    }
    if (node == 0)
      pos--;
    else
      node = link[node];
    remain--;
  }
}
void dfs(int u, int currlen = 0) {
  if (currlen < 0 && to[u].size() > 0) assert(2 > 3);
  if (to[u].empty())
    sum[u] = cost[idx[suff[u]]];
  else
    sum[u] = 0;
  for (auto it : to[u]) {
    int v = it.second, l = fps[v], r = min(cnt - 1, l + len[v] - 1);
    if (dollr[l] <= r)
      dfs(v, -inf),
          ans =
              max(ans, sum[v] * (dollr[l] - l + (dollr[l] > l ? currlen : 0)));
    else
      dfs(v, currlen + r - l + 1);
    sum[u] += sum[v];
  }
  if (currlen < 0) return;
  ans = max(ans, sum[u] * currlen);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n1, i, j, prev1 = 0;
  string s1;
  cin >> n1;
  for (i = 1; i < n1 + 1; i++) {
    cin >> s1;
    for (j = 0; j < s1.size(); j++) add_letter(s1[j]), idx[cnt++] = i;
    add_letter(dollar + i - 1);
    idx[cnt++] = i;
    for (j = prev1; j < cnt; j++) dollr[j] = cnt - 1;
    prev1 = cnt;
  }
  for (i = 1; i < n1 + 1; i++) cin >> cost[i];
  dfs(0);
  cout << ans << endl;
  return 0;
}