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;
struct strings {
  int n, bn;
  vector<string> vs;
  int p[100000];
  int g[22][500000], w[22][500000];
  int gn[500000], gp[500000];
  pair<int, int> via[500000];
  void suffixArray() {
    n = 0;
    for (int i = 0, sn = vs.size(); i < sn; ++i) {
      p[i] = n;
      n += vs[i].size();
    }
    bn = 1;
    while ((1 << (bn - 1)) < n) bn++;
    for (int i = 0; i < n; ++i) {
      gp[i] = gn[i] = 0;
    }
    for (int i = 0, sn = vs.size(); i < sn; ++i) {
      for (int j = 0, stn = vs[i].size(); j < stn; ++j) {
        gn[vs[i][j] - 'a' + 1]++;
        via[p[i] + j] = {i, j};
      }
    }
    for (int i = 1; i < n; ++i) gp[i] = gp[i - 1] + gn[i - 1];
    for (int i = 0; i < n; ++i)
      w[0][gp[vs[via[i].first][via[i].second] - 'a' + 1]++] = i;
    for (int i = 0, gc = 0; i < n; ++i) {
      if (i != 0 && vs[via[w[0][i]].first][via[w[0][i]].second] !=
                        vs[via[w[0][i - 1]].first][via[w[0][i - 1]].second])
        gc++;
      g[0][w[0][i]] = gc;
    }
    for (int i = 1; i < bn; ++i) {
      for (int j = 0; j < n; ++j) {
        gn[j] = 0;
        gp[j] = 0;
      }
      for (int j = 0; j < n; ++j) gn[g[i - 1][j]]++;
      for (int j = 1; j < n; ++j) gp[j] = gp[j - 1] + gn[j - 1];
      for (int j = 0; j < n; ++j)
        if (via[w[i - 1][j]].second + (1 << (i - 1)) >=
            vs[via[w[i - 1][j]].first].size())
          w[i][gp[g[i - 1][w[i - 1][j]]]++] = w[i - 1][j];
      for (int j = 0; j < n; ++j)
        if (via[w[i - 1][j]].second - (1 << (i - 1)) >= 0)
          w[i][gp[g[i - 1][w[i - 1][j] - (1 << (i - 1))]]++] =
              w[i - 1][j] - (1 << (i - 1));
      for (int j = 0, gc = 0; j < n; ++j) {
        if (j > 0) {
          if (g[i - 1][w[i][j - 1]] < g[i - 1][w[i][j]])
            gc++;
          else {
            int gs1 = (via[w[i][j - 1]].second + (1 << (i - 1)) <
                       vs[via[w[i][j - 1]].first].size())
                          ? (g[i - 1][w[i][j - 1] + (1 << (i - 1))])
                          : (-1);
            int gs2 = (via[w[i][j]].second + (1 << (i - 1)) <
                       vs[via[w[i][j]].first].size())
                          ? (g[i - 1][w[i][j] + (1 << (i - 1))])
                          : (-1);
            if (gs1 < gs2) gc++;
          }
        }
        g[i][w[i][j]] = gc;
      }
    }
  }
  int lcp(int a, int b) {
    int ret = 0, la = vs[via[a].first].size() - via[a].second,
        lb = vs[via[b].first].size() - via[b].second;
    if (g[bn - 1][a] == g[bn - 1][b]) return la;
    for (int i = bn - 1; i >= 0; --i) {
      if (g[i][a] == g[i][b]) {
        ret += (1 << i);
        a += (1 << i);
        b += (1 << i);
        if (ret >= la || ret >= lb) break;
      }
    }
    return ret;
  }
};
int n;
char tmp[500000 + 1];
long long int c[100000 + 1], sum[500000 + 1];
strings s;
vector<pair<int, int> > ev;
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%s", tmp);
    s.vs.push_back(string(tmp));
  }
  for (int i = 0; i < n; ++i) scanf("%lld", &c[i]);
  s.suffixArray();
  for (int i = 0; i < s.n; ++i) {
    sum[i] = ((i > 0) ? (sum[i - 1]) : (0)) + c[s.via[s.w[s.bn - 1][i]].first];
    if (i > 0) {
      ev.push_back({s.lcp(s.w[s.bn - 1][i - 1], s.w[s.bn - 1][i]), i});
    }
  }
  sort(ev.begin(), ev.end());
  set<int> seg;
  seg.insert(0);
  seg.insert(s.n - 1);
  long long int res = 0;
  for (int i = 0; i < s.n; ++i) {
    int la = (i == 0) ? (0) : (s.lcp(s.w[s.bn - 1][i - 1], s.w[s.bn - 1][i]));
    int lb = s.vs[s.via[s.w[s.bn - 1][i]].first].size() -
             s.via[s.w[s.bn - 1][i]].second;
    int lc =
        (i == s.n - 1) ? (0) : (s.lcp(s.w[s.bn - 1][i], s.w[s.bn - 1][i + 1]));
    if (la < lb && lc < lb) {
      res = max(res, (long long int)lb * c[s.via[s.w[s.bn - 1][i]].first]);
    }
  }
  for (int i = 0, en = ev.size(); i < en; ++i) {
    int ii = i;
    for (; i < en && ev[ii].first == ev[i].first; ++i) {
      set<int>::iterator it1 = seg.lower_bound(ev[i].second),
                         it2 = seg.lower_bound(ev[i].second);
      it1--;
      long long int cp =
          (sum[*it2] - (((*it1) == 0) ? (0) : (sum[(*it1) - 1])));
      res = max(res, ev[i].first * cp);
    }
    i--;
    for (int j = ii; j <= i; ++j) {
      seg.insert(ev[j].second - 1);
      seg.insert(ev[j].second);
    }
  }
  printf("%lld\n", res);
  return 0;
}