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 rint() {
  int x = 0, f = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && (ch != '-')) ch = getchar();
  if (ch == '-') f = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return f * x;
}
char rchar() {
  char ch = getchar();
  while (ch < 'A' || ch > 'Z') ch = getchar();
  return ch;
}
void juege() {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
}
void swap(int& x, int& y) {
  int t;
  t = x;
  x = y;
  y = t;
}
int min(int x, int y) { return (x < y) ? x : y; }
double min(double x, double y) { return (x < y) ? x : y; }
int max(int x, int y) { return (x > y) ? x : y; }
double max(double x, double y) { return (x > y) ? x : y; }
int c[500005], n;
vector<char> s[500005];
char now[500005];
long long res = 0;
namespace SAM {
int son[500005 << 1][26], pre[500005 << 1], dep[500005 << 1], rot, lst, cnt;
long long r[500005 << 1];
void prepare() { rot = lst = cnt = 1; }
int Newnode(int d) {
  dep[++cnt] = d;
  return cnt;
}
void insert(int idx, int x) {
  int p = lst, np = Newnode(dep[p] + 1);
  while (p && !son[p][x]) son[p][x] = np, p = pre[p];
  if (!p)
    pre[np] = rot;
  else {
    int q = son[p][x];
    if (dep[q] == dep[p] + 1)
      pre[np] = q;
    else {
      int nq = Newnode(dep[p] + 1);
      memcpy(son[nq], son[q], sizeof(son[q]));
      pre[nq] = pre[q];
      pre[q] = pre[np] = nq;
      while (p && son[p][x] == q) son[p][x] = nq, p = pre[p];
    }
  }
  lst = np;
}
int sum[500005 << 1], que[500005 << 1];
void work() {
  memset(sum, 0, sizeof(sum));
  memset(que, 0, sizeof(que));
  for (int i = (1); i <= (cnt); i++) sum[dep[i]]++;
  for (int i = (1); i <= (cnt); i++) sum[i] += sum[i - 1];
  for (int i = (cnt); i >= (1); i--) que[sum[dep[i]]--] = i;
  for (int i = (cnt); i >= (1); i--) r[pre[que[i]]] += r[que[i]];
}
void dfs(int now) {
  for (int i = (1); i <= (cnt); i++) {
    if (r[i] * (dep[i]) > res) res = r[i] * (dep[i]);
  }
}
void YFFF(int idx) {
  int now = rot;
  for (int i = (0); i < (s[idx].size()); i++) {
    now = son[now][s[idx][i] - 'a'];
    r[now] += c[idx];
  }
}
}  // namespace SAM
int main() {
  n = rint();
  for (int i = (1); i <= (n); i++) {
    scanf("%s", now);
    int len = strlen(now);
    for (int j = (0); j < (len); j++) s[i].push_back(now[j]);
  }
  for (int i = (1); i <= (n); i++) c[i] = rint();
  SAM::prepare();
  for (int i = (1); i <= (n); i++) {
    for (int j = (0); j < (s[i].size()); j++) SAM::insert(i, s[i][j] - 'a');
    SAM::lst = SAM::rot;
  }
  for (int i = (1); i <= (n); i++) SAM::YFFF(i);
  SAM::work();
  SAM::dfs(SAM::rot);
  printf("%lld\n", res);
  return 0;
}