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;
long long c[(1 << 20)];
struct SuffixTree {
  int s[(1 << 20)];
  map<int, int> to[(1 << 20)];
  int len[(1 << 20)] = {(1 << 30)}, fpos[(1 << 20)], link[(1 << 20)],
                id[(1 << 20)];
  int node, pos, sz = 1, n = 0;
  int make_node(int p, int l, int k) {
    fpos[sz] = p;
    len[sz] = l;
    id[sz] = k;
    return sz++;
  }
  void go_edge() {
    while (pos > len[to[node][s[n - pos]]]) {
      node = to[node][s[n - pos]];
      pos -= len[node];
    }
  }
  void add(int c, int k) {
    s[n++] = c;
    pos++;
    int last = 0;
    while (pos > 0) {
      go_edge();
      int edge = s[n - pos];
      int& v = to[node][edge];
      int t = s[fpos[v] + pos - 1];
      if (v == 0) {
        v = make_node(n - pos, (1 << 30), k);
        link[last] = node;
        last = 0;
      } else if (t == c) {
        link[last] = node;
        return;
      } else {
        int u = make_node(fpos[v], pos - 1, k);
        to[u][c] = make_node(n - 1, (1 << 30), k);
        to[u][t] = v;
        fpos[v] += pos - 1;
        len[v] -= pos - 1;
        v = u;
        link[last] = u;
        last = u;
      }
      if (node == 0)
        pos--;
      else
        node = link[node];
    }
  }
  long long rr;
  int asd[(1 << 20)];
  long long dfs(int x, int d) {
    long long r = 0;
    d += len[x];
    if (!((int)(to[x]).size()))
      r = c[id[x]];
    else {
      for (auto p : to[x]) r += dfs(p.second, d);
    }
    if (len[x]) rr = max(rr, r * d);
    return r;
  }
  long long doit() {
    for (int i = n - 1; i >= 0; --i) {
      if (s[i] <= 0)
        asd[i] = 0;
      else
        asd[i] = asd[i + 1] + 1;
    }
    for (int i = 1, ThxDem = sz; i < ThxDem; ++i)
      len[i] = min(len[i], asd[fpos[i]]);
    len[0] = 0;
    rr = 0;
    dfs(0, 0);
    return rr;
  }
};
int n;
SuffixTree t;
char _s[(1 << 20)];
int main() {
  scanf("%d", &n);
  for (int i = 0, ThxDem = n; i < ThxDem; ++i) {
    scanf("%s", _s);
    for (int j = 0; _s[j]; ++j) {
      t.add(_s[j], i);
    }
    t.add(-i, i);
  }
  for (int i = 0, ThxDem = n; i < ThxDem; ++i) scanf("%lld", c + i);
  printf("%lld\n", t.doit());
  return 0;
}