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 = 100001;
const int MAXS = 500001;
const int MAXNS = MAXN + MAXS;
const int MAXST = MAXNS * 2;
int n;
string s[MAXN];
int c[MAXN];
char buf[MAXS];
int len;
int a[MAXNS];
long long ans;
struct node {
  int l, r;
  int fa, lnk;
  map<int, int> sons;
  node(int l = 0, int r = 0, int fa = -1) : l(l), r(r), fa(fa) {
    lnk = -1;
    sons.clear();
  }
  int len() { return r - l; }
};
struct v_node {
  int v;
  int len;
  v_node(int v = 0, int len = 0) : v(v), len(len) {}
};
int stn;
node st[MAXST];
v_node active;
set<pair<int, int>> pos;
void init() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%s", buf);
    s[i] = buf;
  }
  for (int i = 0; i < n; ++i) scanf("%d", &c[i]);
  len = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < s[i].size(); ++j) {
      a[len++] = s[i][j] - 'a';
    }
    pos.insert(make_pair(len, c[i]));
    a[len++] = 26 + i;
  }
}
inline bool vnode_full(v_node vnode) { return vnode.len == st[vnode.v].len(); }
bool vnode_extend(v_node &vnode, int i) {
  if (vnode_full(vnode)) {
    if (st[vnode.v].sons.count(a[i])) {
      vnode.v = st[vnode.v].sons[a[i]];
      vnode.len = 0;
    } else {
      return false;
    }
  }
  if (a[st[vnode.v].l + vnode.len] == a[i]) {
    ++vnode.len;
  } else {
    return false;
  }
  return true;
}
int node_split(v_node vnode, int i) {
  int mid = vnode.v;
  if (!vnode_full(vnode)) {
    mid = stn++;
    int L = st[vnode.v].l;
    int M = L + vnode.len;
    st[mid] = node(L, M, st[vnode.v].fa);
    st[mid].lnk = 0;
    st[st[vnode.v].fa].sons[a[L]] = mid;
    st[vnode.v].l = M;
    st[vnode.v].fa = mid;
    st[mid].sons.clear();
    st[mid].sons[a[M]] = vnode.v;
  }
  st[stn] = node(i, len, mid);
  st[mid].sons[a[i]] = stn;
  ++stn;
  return mid;
}
void st_extend(int i) {
  int last = -1;
  while (!vnode_extend(active, i)) {
    int mid = node_split(active, i);
    if (last != -1) {
      st[last].lnk = mid;
    }
    last = mid;
    if (active.v == 0) return;
    if (st[mid].fa == 0) {
      if (active.len == 1) {
        active.v = 0;
        active.len = 0;
      } else {
        --active.len;
        active.v = st[0].sons[a[i - active.len]];
      }
    } else {
      active.v = st[st[st[mid].fa].lnk].sons[a[i - active.len]];
    }
    while (active.len > st[active.v].len()) {
      active.len -= st[active.v].len();
      active.v = st[active.v].sons[a[i - active.len]];
    }
  }
  if (last != -1) st[last].lnk = st[active.v].fa;
}
void build_tree() {
  st[0] = node();
  stn = 1;
  active = v_node(0, 0);
  for (int i = 0; i < len; ++i) {
    st_extend(i);
  }
}
long long dfs(int i, int len) {
  long long sum = 0;
  auto it = pos.lower_bound(make_pair(st[i].l, INT_MIN));
  if (it != pos.end() && it->first < st[i].r) {
    sum += it->second;
    if (it->first > st[i].l) {
      len += it->first - st[i].l;
      if (ans < sum * len) ans = sum * len;
    }
    return sum;
  }
  len += st[i].len();
  for (map<int, int>::iterator it = st[i].sons.begin(); it != st[i].sons.end();
       ++it) {
    sum += dfs(it->second, len);
  }
  if (ans < sum * len) ans = sum * len;
  return sum;
}
int dfs2(int i, int len) {
  long long sum = 0;
  auto it = pos.lower_bound(make_pair(st[i].l, INT_MIN));
  if (it != pos.end() && it->first < st[i].r) {
    sum += it->second;
    if (it->first > st[i].l) {
      len -= st[i].r - it->first;
      if (ans < sum * len) ans = sum * len;
    }
    return sum;
  }
  for (map<int, int>::iterator it = st[i].sons.begin(); it != st[i].sons.end();
       ++it) {
    sum += dfs(it->second, len + st[it->second].len());
  }
  if (ans < sum * len) ans = sum * len;
  return sum;
}
void solve() {
  build_tree();
  dfs(0, 0);
}
void print() { cout << ans << endl; }
int main() {
  init();
  solve();
  print();
}