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>
#pragma GCC optimize("Ofast")
using namespace std;
constexpr long long MOD = 1000000007LL;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class C>
struct SuffixAutomaton {
  struct State {
    int len, link;
    map<C, int> nex;
    State(int len, int link) : len(len), link(link) {}
  };
  vector<State> st;
  vector<long long> dp;
  int last;
  SuffixAutomaton() : last(0) {
    st.emplace_back(0, -1);
    dp.emplace_back(0);
  }
  int add(C c, long long val, int cur = -1) {
    if (cur == -1) {
      cur = last;
    }
    if (st[cur].nex.count(c) && st[st[cur].nex[c]].len == st[cur].len + 1) {
      int q = st[cur].nex[c];
      dp[q] += val;
      return last = q;
    }
    int p = cur;
    int nex = st.size();
    st.emplace_back(st[p].len + 1, 0);
    dp.emplace_back(val);
    while (p != -1 && !st[p].nex.count(c)) {
      st[p].nex[c] = nex;
      p = st[p].link;
    }
    if (p == -1) {
      st[nex].link = 0;
      return last = nex;
    }
    int q = st[p].nex[c];
    if (st[p].len + 1 == st[q].len) {
      st[nex].link = q;
    } else {
      int clone = st.size();
      st.emplace_back(st[q]);
      dp.emplace_back(0);
      st[clone].len = st[p].len + 1;
      while (p != -1 && st[p].nex[c] == q) {
        st[p].nex[c] = clone;
        p = st[p].link;
      }
      st[q].link = st[nex].link = clone;
    }
    return last = nex;
  }
  vector<int> topologicalsort() {
    vector<int> ret;
    vector<int> deg(st.size());
    for (int i = 0; i < st.size(); i++) {
      for (auto &p : st[i].nex) deg[p.second]++;
    }
    queue<int> que;
    que.emplace(0);
    while (!que.empty()) {
      int v = que.front();
      que.pop();
      ret.emplace_back(v);
      for (auto &p : st[v].nex) {
        if (--deg[p.second] == 0) que.emplace(p.second);
      }
    }
    return ret;
  }
  vector<int> suffixtree() {
    vector<int> ret;
    vector<vector<int>> G(st.size());
    for (int i = 1; i < st.size(); i++) G[st[i].link].emplace_back(i);
    queue<int> que;
    que.emplace(0);
    while (!que.empty()) {
      int v = que.front();
      que.pop();
      ret.emplace_back(v);
      for (auto nv : G[v]) que.emplace(nv);
    }
    return ret;
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  SuffixAutomaton<char> SA;
  int N;
  cin >> N;
  vector<string> S(N);
  vector<int> C(N);
  for (int i = 0; i < (N); ++i) cin >> S[i];
  for (int i = 0; i < (N); ++i) cin >> C[i];
  for (int i = 0; i < (N); ++i) {
    int cur = 0;
    for (auto c : S[i]) {
      cur = SA.add(c, C[i], cur);
    }
  }
  auto A = SA.suffixtree();
  int M = A.size();
  long long ans = 0;
  for (int i = M - 1; i >= 0; i--) {
    if (i) SA.dp[SA.st[A[i]].link] += SA.dp[A[i]];
    chmax(ans, SA.dp[A[i]] * SA.st[A[i]].len);
  }
  cout << ans << '\n';
}