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 MAXN = 6e5 + 1000;
int ALP = 26;
struct AState {
  map<int, int> next;
  int suffixLink;
  int maxLen;
  long long cost = 0;
  int pos = 0;
  AState() {
    suffixLink = -1;
    maxLen = 0;
  }
};
AState automathon[2 * MAXN];
int lastUsed = 0;
int curVer = 0;
int lastVer = 0;
void preBuild() {
  lastVer = curVer = 0;
  automathon[curVer].suffixLink = -1;
  automathon[curVer].maxLen = 0;
}
vector<vector<int>> verH;
void addSymToAutomathon(int pos, int sym, int cost) {
  lastUsed++;
  int lastVer = lastUsed;
  automathon[lastVer].maxLen = pos + 1;
  automathon[lastVer].cost = cost;
  automathon[lastVer].pos = pos;
  int p = curVer;
  while (p != -1) {
    if (automathon[p].next.count(sym) == 0) {
      automathon[p].next[sym] = lastVer;
      p = automathon[p].suffixLink;
    } else {
      break;
    }
  }
  if (p == -1) {
    automathon[lastVer].suffixLink = 0;
  } else {
    int q = automathon[p].next[sym];
    if (automathon[p].maxLen + 1 == automathon[q].maxLen) {
      automathon[lastVer].suffixLink = q;
    } else {
      int clone = ++lastUsed;
      automathon[clone] = automathon[q];
      automathon[clone].maxLen = automathon[p].maxLen + 1;
      automathon[q].suffixLink = clone;
      automathon[clone].cost = 0;
      while (p != -1 && automathon[p].next.count(sym) &&
             automathon[p].next[sym] == q) {
        automathon[p].next[sym] = clone;
        p = automathon[p].suffixLink;
      }
      automathon[lastVer].suffixLink = clone;
      verH[automathon[clone].maxLen].push_back(clone);
    }
  }
  curVer = lastVer;
  verH[automathon[curVer].maxLen].push_back(curVer);
}
int lf[2 * MAXN];
int bad[2 * MAXN];
vector<string> ss;
int main(void) {
  preBuild();
  int n;
  cin >> n;
  int sumSize = 0;
  for (int i = 0; i < n; i++) {
    string si;
    cin >> si;
    ss.push_back(si);
    sumSize += si.size() + 1;
  }
  verH.resize(sumSize + 1);
  int pos = 0;
  for (int i = 0; i < n; i++) {
    int cost;
    cin >> cost;
    {
      bad[pos] = true;
      lf[pos] = pos;
      addSymToAutomathon(pos, ALP++, -1e9);
      pos++;
    }
    for (char c : ss[i]) {
      lf[pos] = pos == 0 ? 0 : lf[pos - 1];
      addSymToAutomathon(pos, c - 'a', cost);
      pos++;
    }
  }
  int maxH = sumSize;
  long long ans = 0;
  for (int i = maxH; i >= 1; i--) {
    for (int ver : verH[i]) {
      int pr = automathon[ver].suffixLink;
      automathon[pr].cost += automathon[ver].cost;
      int lng = automathon[ver].maxLen;
      if (automathon[ver].pos - lng + 1 <= lf[automathon[ver].pos]) {
        lng = automathon[ver].pos - lf[automathon[ver].pos];
      }
      if (lng > automathon[pr].maxLen) {
        ans = max(ans, lng * 1LL * automathon[ver].cost);
      }
    }
  }
  cout << ans << endl;
  return 0;
}