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;
using INT = long long;
const int NN = 1000001;
int ord[NN * 2], cnt[NN];
const int sma = 26;
struct automaton {
  int sz, ed;
  INT ans;
  struct node {
    int deep, fail, nxt[sma];
    INT val;
    void clear() {
      for (int i = 0; i < sma; i++) nxt[i] = -1;
      fail = 0;
      deep = 0;
      val = 0;
    }
  } mem[NN * 2];
  void init() {
    mem[1].clear();
    mem[0].clear();
    for (int i = 0; i < sma; i++) mem[0].nxt[i] = 1;
    mem[0].deep = -1;
    sz = 2;
    ed = 1;
    ans = 0;
    return;
  }
  void insert(int c, int w) {
    if (mem[ed].nxt[c] != -1) {
      int p1 = mem[ed].nxt[c];
      if (mem[p1].deep == mem[ed].deep + 1) {
        mem[p1].val += w;
        ed = p1;
        return;
      }
      int p2 = sz++;
      mem[p2] = mem[p1];
      mem[p2].val = w;
      mem[p2].deep = mem[ed].deep + 1;
      mem[p1].fail = p2;
      while (ed != -1 and mem[ed].nxt[c] == p1) {
        mem[ed].nxt[c] = p2;
        ed = mem[ed].fail;
      }
      ed = p2;
      return;
    }
    int p = sz++;
    mem[p].clear();
    mem[p].deep = mem[ed].deep + 1;
    mem[p].val = w;
    while (mem[ed].nxt[c] == -1) {
      mem[ed].nxt[c] = p;
      ed = mem[ed].fail;
    }
    int p1 = mem[ed].nxt[c];
    if (mem[p1].deep == mem[ed].deep + 1)
      mem[p].fail = p1;
    else {
      int p2 = sz++;
      mem[p2] = mem[p1];
      mem[p2].val = 0;
      mem[p2].deep = mem[ed].deep + 1;
      mem[p1].fail = mem[p].fail = p2;
      while (mem[ed].nxt[c] == p1) {
        mem[ed].nxt[c] = p2;
        ed = mem[ed].fail;
      }
    }
    ed = p;
    return;
  }
  void build(int n) {
    for (int i = 0; i < n + 3; i++) cnt[i] = 0;
    for (int i = 1; i < sz; i++) cnt[mem[i].deep]++;
    for (int i = 1; i < n + 3; i++) cnt[i] += cnt[i - 1];
    for (int i = 1; i < sz; i++) ord[--cnt[mem[i].deep]] = i;
    for (int i = sz - 2; i >= 0; i--) {
      int cur = ord[i];
      int prv = mem[cur].fail;
      if (~prv) mem[prv].val += mem[cur].val;
    }
    return;
  }
  INT solve() {
    for (int i = 1; i < sz; i++) {
      ans = max(ans, 1ll * mem[i].deep * mem[i].val);
    }
    return ans;
  }
} sam;
char s[NN];
string str[NN];
int cost[NN];
int main() {
  sam.init();
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    scanf("%s", s);
    str[i] = s;
  }
  int l = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", cost + i);
    l += str[i].length();
    sam.ed = 1;
    for (int j = 0; j < str[i].length(); j++) {
      sam.insert(str[i][j] - 'a', cost[i]);
    }
  }
  sam.build(l);
  cout << sam.solve();
  return 0;
}