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, ns, en = 1;
string S[NS];
long long val[N];
struct edge {
  int a, b;
  int v, si;
  inline int len() { return b - a + 1; }
  inline char operator[](int i) { return S[si][a + i]; }
  string str() { return S[si].substr(a, len()); }
} ce;
int suf[N], p[N];
map<char, edge> tr[N];
int si = -1;
void sufftree(string s) {
  s += '$';
  S[++si] = s;
  ns = cn = cd = 0;
  int i = 0, j, n = s.size();
  for (j = 0; j < n; j++)
    for (; i <= j; i++) {
      if (ns && !cd) suf[ns] = cn, ns = 0;
      if (cd ? ce[cd] == s[j] : tr[cn].count(s[j])) {
        if (cd++ == 0) ce = tr[cn][s[j]];
        if (cd == ce.len()) cd = 0, cn = ce.v;
        break;
      } else if (cd) {
        if (ns) suf[ns] = en;
        tr[en][ce[cd]] = {ce.a + cd, ce.b, ce.v, ce.si};
        tr[en][s[j]] = {j, n - 1, en + 1, si};
        tr[cn][ce[0]] = {ce.a, ce.a + cd - 1, en, ce.si};
        p[en] = cn;
        p[en + 1] = p[ce.v] = en;
        ns = en;
        en += 2;
        int g = cn ? j - cd : i + 1;
        cn = suf[cn];
        while (g < j && g + tr[cn][s[g]].len() <= j) {
          ce = tr[cn][s[g]];
          cn = ce.v;
          g += ce.len();
        }
        cd = j - g;
        if (cd) ce = tr[cn][s[g]];
      } else {
        p[en] = cn;
        tr[cn][s[j]] = {j, n - 1, en++, si};
        cn = suf[cn];
      }
    }
}
void clear_all() {
  for (int i = 0; i < en; i++) tr[i].clear();
  en = 1;
  si = -1;
}
void proc(string &s, int si, int c) {
  cn = cd = 0;
  for (char c : s) {
    if (cd++ == 0) ce = tr[cn][c];
    if (cd == ce.len()) cd = 0, cn = ce.v;
  }
  val[cn] += c;
  for (int i = 1; i < s.size(); i++) {
    cn = p[cn];
    int g = cn ? s.size() - ce.len() : i;
    cn = suf[cn];
    while (g != s.size()) {
      ce = tr[cn][s[g]];
      g += ce.len();
      cn = ce.v;
    }
    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.v, 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);
  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);
}