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>
#pragma GCC optimize("Ofast")
using namespace std;
template <typename T>
void read(T &x) {
  x = 0;
  char ch = getchar();
  long long f = 1;
  while (!isdigit(ch)) {
    if (ch == '-') f *= -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - 48;
    ch = getchar();
  }
  x *= f;
}
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
struct SuffixAutomaton {
  static const int M = 2000010;
  int sz, lst;
  int ch[M][27];
  int len[M], link[M], mi[M];
  long long vl[M];
  void init() {
    create(0);
    lst = 0;
  }
  int create(int id = 0) {
    memset(ch[id], 0, sizeof(ch[0]));
    len[id] = link[id] = mi[id] = 0;
    vl[id] = 0;
    return sz = id;
  }
  void extend(const char *s, int id, int cost) {
    for (int i = 0; s[i]; ++i) {
      int c = s[i] - 'a';
      int cur = create(sz + 1);
      mi[cur] = i + 1;
      len[cur] = len[lst] + 1;
      vl[cur] = cost;
      int p = lst;
      while (ch[p][c] == 0) {
        ch[p][c] = cur;
        p = link[p];
      }
      if (ch[p][c] != cur) {
        int q = ch[p][c];
        if (len[p] + 1 == len[q]) {
          link[cur] = q;
        } else {
          int clone = create(sz + 1);
          memcpy(ch[clone], ch[q], sizeof(ch[q]));
          link[clone] = link[q];
          len[clone] = len[p] + 1;
          mi[clone] = min(mi[q], len[clone]);
          while (ch[p][c] == q) {
            ch[p][c] = clone;
            p = link[p];
          }
          link[q] = link[cur] = clone;
        }
      }
      lst = cur;
    }
  }
  long long build() {
    long long ans = 0;
    vector<int> nodes;
    for (int i = 1; i <= sz; ++i) nodes.push_back(i);
    sort(nodes.begin(), nodes.end(),
         [&](int a, int b) { return len[a] > len[b]; });
    for (auto u : nodes) {
      int v = link[u];
      vl[v] += vl[u];
      if (mi[u] > len[v]) ans = max(ans, vl[u] * mi[u]);
    }
    return ans;
  }
} SAM;
string s[100010];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int n;
  int x;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> s[i];
  for (int i = 1; i <= n; ++i) {
    cin >> x;
    SAM.extend(s[i].c_str(), i, x);
    SAM.extend("{", 1, 0);
  }
  cout << SAM.build();
  return 0;
}