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;
template <typename T>
inline T abs(T t) {
  return t < 0 ? -t : t;
}
const long long modn = 1000000007;
inline long long mod(long long x) { return x % modn; }
namespace sf {
const int NS = 112345;
const int N = 1123456;
int cn, cd, cc, li, ns, en, es[N];
inline int r(int b, int si) { return b == N ? es[si] : b; }
string s[NS];
struct edge {
  int a, b;
  int n, si;
  inline int len() { return r(b, si) - a + 1; }
  inline char operator[](int i) { return s[si][a + i]; }
  inline string str() { return s[si].substr(a, b - a + 1); }
};
int suf[N], p[N];
long long val[N];
map<char, edge> tr[N];
int si;
void add() {
  int &e = es[si];
  string &s = sf::s[si];
  e++;
  for (; li <= e; li++) {
    if (ns && cd == 0) suf[ns] = cn, ns = 0;
    if (cd ? tr[cn][cc][cd] == s[e] : tr[cn].count(s[e])) {
      if (cd++ == 0) cc = s[e];
      if (cd == tr[cn][cc].len()) cd = 0, cn = tr[cn][cc].n;
      break;
    }
    tr[en].clear();
    if (cd) {
      if (ns) suf[ns] = en;
      tr[en + 1].clear();
      edge &ed = tr[cn][cc];
      char w = ed[cd];
      tr[en][w] = ed;
      tr[en][w].a += cd;
      tr[en][s[e]] = edge{e, N, en + 1, si};
      p[en] = cn;
      p[en + 1] = p[tr[cn][cc].n] = en;
      ns = en;
      ed.b = ed.a + cd - 1;
      ed.n = en++;
      en++;
      int g = cn ? e - cd : li + 1;
      cn = suf[cn];
      while (tr[cn].count(cc = s[g]) && g + tr[cn][s[g]].len() <= e) {
        g += tr[cn][cc].len();
        cn = tr[cn][cc].n;
      }
      cd = e - g;
    } else {
      p[en] = cn;
      tr[cn][s[e]] = edge{e, N, en++, si};
      cn = suf[cn];
    }
  }
}
void reset() {
  tr[0].clear();
  en = 1;
  si = -1;
}
void sufftree(string ss) {
  si++;
  es[si] = -1;
  ss += '$';
  s[si] = ss;
  ns = cn = cd = cc = li = 0;
  for (int i = 0; i < ss.size(); i++) add();
}
void proc(string &s, int si, int c) {
  cn = cc = cd = 0;
  for (char c : s) {
    if (cd++ == 0) cc = c;
    if (cd == tr[cn][cc].len()) cd = 0, cn = tr[cn][cc].n;
  }
  val[cn] += c;
  for (int i = 1; i < s.size(); i++) {
    cn = p[cn];
    int g = cn ? s.size() - tr[cn][cc].len() : i;
    cn = suf[cn];
    while (g != s.size()) {
      cc = s[g];
      g += tr[cn][cc].len();
      cn = tr[cn][cc].n;
    }
    val[cn] += c;
  }
}
long long mx = 0;
long long dfs(int u, long long sz) {
  for (auto &e : tr[u]) val[u] += dfs(e.second.n, sz + e.second.len());
  if (tr[u].empty()) sz--;
  mx = max(mx, val[u] * sz);
  return val[u];
}
};  // namespace sf
char s[500009];
int main() {
  int i, n, x;
  scanf("%d", &n);
  sf::reset();
  for (i = 0; i < n; i++) {
    scanf("%s", s);
    sf::sufftree(s);
  }
  for (i = 0; i < n; i++) {
    scanf("%d", &x);
    sf::proc(sf::s[i], i, x);
  }
  sf::dfs(0, 0);
  printf("%I64d\n", sf::mx);
}