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 = 2e6 + 10, M = 21;
char t[maxn];
int a[maxn], b[maxn], c[M][maxn], n, sa[maxn], lg[maxn];
int sz[maxn], la[maxn], lef[maxn], rig[maxn], len[maxn];
long long ps[maxn];
pair<pair<int, int>, int> v[maxn];
int lcp(int x, int y) {
  int mx = min(len[x], len[y]), ans = 0;
  for (int i = lg[mx]; i >= 0; i--) {
    if (c[i][x] == c[i][y]) {
      x += (1 << i);
      y += (1 << i);
      ans += (1 << i);
    }
  }
  return min(ans, mx);
}
int main() {
  cin >> n;
  string s;
  for (int i = 2; i < maxn; i++) lg[i] = lg[i / 2] + 1;
  for (int i = 0; i < n; i++) {
    scanf("%s", t);
    int m = strlen(t);
    sz[i] = m;
    for (int j = 0; j < m; j++) {
      s += t[j];
      a[s.size() - 1] = i;
    }
    s += '|';
    a[s.size() - 1] = maxn - 1;
  }
  for (int i = 0; i < n; i++) scanf("%d", b + i);
  n = s.size();
  for (int i = n; i--;) len[i] = (s[i] == '|' ? 0 : len[i + 1] + 1);
  for (int i = 0; i < n; i++) c[0][i] = s[i];
  for (int i = 1; i <= 20; i++) {
    for (int j = 0; j < n; j++)
      if (j + (1 << (i - 1)) >= n)
        v[j] = make_pair(make_pair(c[i - 1][j], -1), j);
      else
        v[j] =
            make_pair(make_pair(c[i - 1][j], c[i - 1][j + (1 << (i - 1))]), j);
    sort(v, v + n);
    for (int j = 0; j < n; j++) {
      if (j > 0 && v[j].first == v[j - 1].first)
        c[i][v[j].second] = c[i][v[j - 1].second];
      else
        c[i][v[j].second] = j + 1;
      if (i == 20) sa[j] = v[j].second;
    }
  }
  for (int i = 0; i + 1 < n; i++) la[i] = lcp(sa[i], sa[i + 1]);
  stack<int> st;
  for (int i = 0; i < n - 1; i++) {
    while (st.size() && la[i] <= la[st.top()]) st.pop();
    lef[i] = (st.size() ? st.top() + 1 : 0);
    st.push(i);
  }
  while (st.size()) st.pop();
  for (int i = n - 1; i--;) {
    while (st.size() && la[i] <= la[st.top()]) st.pop();
    rig[i] = (st.size() ? st.top() + 1 : n);
    st.push(i);
  }
  long long jav = 0;
  for (int i = 0; i < n; i++) ps[i + 1] = ps[i] + b[a[sa[i]]];
  for (int i = 0; i < n - 1; i++) {
    jav = max(jav, 1LL * la[i] * (ps[rig[i]] - ps[lef[i]]));
    int t = len[sa[i]];
    if (t && la[i] < t && (!i || la[i - 1] < t))
      jav = max(jav, 1LL * t * b[a[sa[i]]]);
  }
  cout << jav << endl;
}