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 = 612345 * 2;
int cn, cd, ns, en = 1, lst;
string S[NS];
int si = -1;
vector<int> sufn[N];
struct node {
  int l, r, si;
  int p, suf;
  map<char, int> adj;
  node() : l(0), r(-1), suf(0), p(0) {}
  node(int L, int R, int S, int P) : l(L), r(R), si(S), p(P) {}
  inline int len() { return r - l + 1; }
  inline int operator[](int i) { return S[si][l + i]; }
  inline int& operator()(char c) { return adj[c]; }
} t[N];
inline int new_node(int L, int R, int S, int P) {
  t[en] = node(L, R, S, P);
  return en++;
}
void add_string(string s) {
  s += '$';
  S[++si] = s;
  sufn[si].resize(s.size() + 1);
  cn = cd = 0;
  int i = 0;
  const int n = s.size();
  for (int j = 0; j < n; j++)
    for (; i <= j; i++) {
      if (cd == t[cn].len() && t[cn](s[j])) cn = t[cn](s[j]), cd = 0;
      if (cd < t[cn].len() && t[cn][cd] == s[j]) {
        cd++;
        if (j < s.size() - 1)
          break;
        else {
          if (i) t[lst].suf = cn;
          for (; i <= j; i++) {
            sufn[si][i] = cn;
            cn = t[cn].suf;
          }
        }
      } else if (cd == t[cn].len()) {
        sufn[si][i] = en;
        if (i) t[lst].suf = en;
        lst = en;
        t[cn](s[j]) = new_node(j, n - 1, si, cn);
        cn = t[cn].suf;
        cd = t[cn].len();
      } else {
        int mid = new_node(t[cn].l, t[cn].l + cd - 1, t[cn].si, t[cn].p);
        t[t[cn].p](t[cn][0]) = mid;
        if (ns) t[ns].suf = mid;
        if (i) t[lst].suf = en;
        lst = en;
        sufn[si][i] = en;
        t[mid](s[j]) = new_node(j, n - 1, si, mid);
        t[mid](t[cn][cd]) = cn;
        t[cn].p = mid;
        t[cn].l += cd;
        cn = t[mid].p;
        int g = cn ? j - cd : i + 1;
        cn = t[cn].suf;
        while (g < j && g + t[t[cn](S[si][g])].len() <= j)
          cn = t[cn](S[si][g]), g += t[cn].len();
        if (g == j)
          ns = 0, t[mid].suf = cn, cd = t[cn].len();
        else
          ns = mid, cn = t[cn](S[si][g]), cd = j - g;
      }
    }
}
long long mx = 0;
long long val[N];
long long dfs(int u, long long sz) {
  for (auto& e : t[u].adj) val[u] += dfs(e.second, sz + t[e.second].len());
  if (t[u].adj.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::add_string(s);
  }
  for (i = 0; i < n; i++) {
    scanf("%d", &x);
    for (int j = 0; j < sf::S[i].size(); j++) sf::val[sf::sufn[i][j]] += x;
  }
  sf::dfs(0, 0);
  printf("%I64d\n", sf::mx);
}