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;
template <class T>
using min_queue = priority_queue<T, vector<T>, greater<T>>;
const int INF = static_cast<int>(1e9);
const long long INF_LL = static_cast<long long>(4e18);
const double pi = acos(-1.0);
template <class T>
T& smin(T& x, const T& y) {
  if (x > y) x = y;
  return x;
}
template <class T>
T& smax(T& x, const T& y) {
  if (x < y) x = y;
  return x;
}
template <class T>
T sqr(const T& x) {
  return x * x;
}
template <class T>
T gcd(T a, T b) {
  for (a = abs(a), b = abs(b); a && b; a >= b ? a %= b : b %= a)
    ;
  return a + b;
}
template <typename Iterator>
void print(const char* fmt, Iterator first, Iterator last,
           const char* delimiter = " ", const char* closing = "\n") {
  for (; first != last; ++first != last ? printf("%s", delimiter) : 0)
    printf(fmt, *first);
  printf("%s", closing);
}
template <int N, char Aa = 'a', char Az = 'z'>
class SuffixAutomaton {
 public:
  static const int A = Az - Aa + 1;
  struct State {
    int length;
    State *link, *next[A];
    long long sum;
  } state[2 * N - 1];
  State *last, *free;
  int size() const { return static_cast<int>(free - state); }
  void init() {
    last = state;
    free = last + 1;
    fill_n(last->next, A, nullptr);
    last->length = 0;
    last->link = nullptr;
  }
  State* computeLink(State* p, char c) {
    State* q = p->next[c];
    if (p->length + 1 == q->length) return q;
    State* clone = free++;
    clone->length = p->length + 1;
    copy_n(q->next, A, clone->next);
    clone->link = q->link;
    for (; p && p->next[c] == q; p = p->link) p->next[c] = clone;
    return q->link = clone;
  }
  void addLetter(char c, bool newString = false) {
    if (newString) last = state;
    c -= Aa;
    State* p = last;
    if (p->next[c]) {
      last = computeLink(p, c);
      return;
    }
    last = free++;
    fill_n(last->next, A, nullptr);
    last->length = p->length + 1;
    for (; p && !p->next[c]; p = p->link) p->next[c] = last;
    last->link = p ? computeLink(p, c) : state;
  }
  void build(const char* s) {
    for (init(); *s; ++s) addLetter(*s);
  }
};
const int N = 1e5, L = 5e5 + 1;
int n, c[N];
char s[L];
SuffixAutomaton<L, 'a', 'z'> sa;
int split[L + 1], q[2 * L];
int main() {
  cin.tie(NULL);
  scanf("%d", &n);
  char* t = s;
  for (int i(0), b_(n); i < b_; ++i) {
    for (scanf("%s", t); *t; ++t)
      ;
    split[t - s] = 1;
  }
  for (int i(0), b_(n); i < b_; ++i) scanf("%d", c + i);
  sa.init();
  for (int i = 0, u = 0; s[i]; ++i) {
    sa.addLetter(s[i], split[i]);
    if (split[i]) ++u;
    sa.last->sum += c[u];
  }
  memset(split, 0, sizeof split);
  for (int i(0), b_(static_cast<int>((sa).size())); i < b_; ++i)
    ++split[sa.state[i].length + 1];
  for (int i(0), b_(L - 1); i < b_; ++i) split[i + 1] += split[i];
  for (int i(0), b_(static_cast<int>((sa).size())); i < b_; ++i)
    q[split[sa.state[i].length]++] = i;
  long long ans = 0;
  for (int i(static_cast<int>((sa).size()) - 1), b_(1); i >= b_; --i) {
    auto& state = sa.state[q[i]];
    smax(ans, state.sum * state.length);
    state.link->sum += state.sum;
  }
  printf("%lld\n", ans);
  return 0;
}