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;
const int N = 2e6;
struct State {
  map<char, int> nxt;
  int link, len;
} sa[N];
int last, cnt;
void init() {
  last = 0;
  cnt = 1;
  sa[0].link = -1;
  sa[0].len = 0;
}
void addSymbol(char c) {
  int cur = cnt++;
  sa[cur].len = sa[last].len + 1;
  int p = last;
  for (; p != -1 && !sa[p].nxt.count(c); p = sa[p].link) sa[p].nxt[c] = cur;
  if (p == -1) {
    sa[cur].link = 0;
  } else {
    int q = sa[p].nxt[c];
    if (sa[q].len == sa[p].len + 1) {
      sa[cur].link = q;
    } else {
      int clone = cnt++;
      sa[clone] = sa[q];
      sa[clone].len = sa[p].len + 1;
      for (; p != -1 && sa[p].nxt[c] == q; p = sa[p].link) sa[p].nxt[c] = clone;
      sa[q].link = sa[cur].link = clone;
    }
  }
  last = cur;
}
void dbgGraphPrint() {
  cout << string(30, '-') << endl;
  for (int i = 0; i < cnt; ++i)
    for (auto& x : sa[i].nxt)
      cerr << i << " " << x.first << " " << x.second << endl;
  cout << string(30, '-') << endl;
}
void build(const string& s) {
  init();
  for (char c : s) {
    addSymbol(c);
  }
}
char str[N];
long long add[N];
long long f[N];
long long get(int state) {
  long long& res = f[state];
  if (res == -1) {
    res = add[state];
    for (auto x : sa[state].nxt) {
      if (x.first == '#') continue;
      res += get(x.second);
    }
  }
  return res;
}
int minLen[N], maxLen[N];
vector<vector<int>> g;
bool used[N];
int getMinLen(int state) {
  int& res = minLen[state];
  if (res == -1) {
    int mn = -1;
    for (int x : g[state]) {
      int y = getMinLen(x);
      if (mn == -1 || y < mn) mn = y;
    }
    res = mn + 1;
  }
  return res;
}
int getMaxLen(int state) {
  int& res = maxLen[state];
  if (res == -1) {
    int mn = -1;
    for (int x : g[state]) {
      int y = getMaxLen(x);
      if (y > mn) mn = y;
    }
    res = mn + 1;
  }
  return res;
}
long long getAns(int state) {
  if (used[state]) return 0;
  used[state] = true;
  long long cur = 0;
  cur = max(cur, getMaxLen(state) * get(state));
  cur = max(cur, getMinLen(state) * get(state));
  for (auto x : sa[state].nxt) {
    if (x.first == '#') continue;
    cur = max(cur, getAns(x.second));
  }
  return cur;
}
void buildTrGraph() {
  g.assign(cnt, vector<int>());
  for (int i = 0; i < cnt; ++i) {
    for (auto& x : sa[i].nxt) {
      if (x.first != '#') g[x.second].push_back(i);
    }
  }
}
void initAll(const vector<string>& ss) {
  fill(f, f + N, -1);
  for (const auto& s : ss) {
    int st = 0;
    for (char c : s) st = sa[st].nxt[c];
    int x;
    scanf("%d", &x);
    for (int p = st; p != -1; p = sa[p].link) add[p] += x;
  }
  fill(minLen, minLen + N, -1);
  fill(maxLen, maxLen + N, -1);
  buildTrGraph();
}
int main() {
  int n;
  scanf("%d ", &n);
  vector<string> ss;
  for (int i = 0; i < n; ++i) {
    gets(str);
    ss.push_back(str);
  }
  string au = "";
  for (auto& s : ss) {
    au += s;
    au += "#";
  }
  build(au);
  initAll(ss);
  long long ans = getAns(0);
  printf("%I64d", ans);
}