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>
template <int NODE_NUM = 1000000>
class SuffixAutomaton {
  using value_structure = std::string;
  using value_type = char;
  using size_type = std::int32_t;
  struct Node {
    size_type link, len, id, pre, original;
    value_type key;
    std::map<value_type, size_type> next;
    Node(size_type id = 0, value_type key = -1, size_type len = 0,
         size_type link = -1, size_type original = -1)
        : id(id), key(key), link(link), len(len), pre(1), original(original) {}
    void dump() {
      std::cout << "(id, key, len, link, pre cnt): (" << id << ", " << key
                << ", " << len << ", " << link << ", " << pre << ")"
                << std::endl;
      for (auto&& u : next) {
        std::cout << "(char, id): (" << u.first << ", " << u.second << ")"
                  << std::endl;
      }
    }
  };

 private:
  size_type last, len;

 public:
  std::vector<Node> node;
  SuffixAutomaton() : last(0) {
    node.reserve(NODE_NUM);
    node.push_back(Node());
  }
  SuffixAutomaton(const value_structure& s) : SuffixAutomaton() {
    extend_by_string(s);
  }
  void extend(const value_type c, size_type base = -1) {
    if (base >= 0) last = base;
    size_type cur, p = last;
    if (node[last].next.count(c) == 0) {
      node.push_back(Node(node.size(), c, node[last].len + 1));
      cur = node.size() - 1;
    } else {
      cur = node[last].next[c];
    }
    last = cur;
    for (; p != -1 && node[p].next.count(c) == 0; p = node[p].link)
      node[p].next[c] = cur;
    if (p == -1) {
      node[cur].link = 0;
    } else {
      size_type q = node[p].next[c];
      if (node[p].len + 1 == node[q].len) {
        if (q != cur)
          node[cur].link = q;
        else
          node[cur].pre++;
      } else {
        size_type clone = node.size();
        node.push_back(node[q]);
        node[clone].len = node[p].len + 1;
        node[clone].original = q;
        node[clone].id = node.size() - 1;
        node[clone].pre = (q == cur);
        if (q == cur) last = clone;
        for (; p != -1 && node[p].next[c] == q; p = node[p].link)
          node[p].next[c] = clone;
        node[q].link = node[cur].link = clone;
      }
    }
  }
  void extend_by_string(const value_structure& s, size_type base = -1) {
    for (int i = 0; i < s.size(); i++) {
      extend(s[i], (i == 0 ? base : -1));
    }
  }
  void topological_sort() {
    std::vector<size_type> indeg(node.size(), 0), ord(node.size());
    std::vector<Node> node2(node.size());
    size_type p = 1;
    for (auto&& v : node) {
      for (auto&& u : v.next) {
        indeg[u.second]++;
      }
    }
    node2[0] = node[0];
    ord[0] = 0;
    for (int i = 0; i < node.size(); i++) {
      for (auto&& u : node2[i].next) {
        if (--indeg[u.second] == 0) {
          ord[u.second] = p;
          node2[p++] = node[u.second];
        }
      }
    }
    for (auto&& v : node2) {
      v.link = v.link == -1 ? -1 : ord[v.link];
      v.original = ord[v.original];
      for (auto&& u : v.next) {
        u.second = ord[u.second];
      }
    }
    swap(node, node2);
  }
  Node& operator[](size_type k) { return node[k]; }
  const size_type size() { return node.size(); }
  void dump() {
    std::cout << "---------------------------------------------------------"
              << std::endl;
    for (int i = 0; i < node.size(); i++) {
      std::cout << "id: " << i << std::endl;
      node[i].dump();
    }
    std::cout << "---------------------------------------------------------"
              << std::endl;
  }
};
SuffixAutomaton<> sa;
int main() {
  using namespace std;
  cin.tie(0);
  ios::sync_with_stdio(false);
  sa = SuffixAutomaton<>();
  int64_t n;
  cin >> n;
  vector<string> s(n);
  vector<int64_t> c(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    sa.extend_by_string(s[i], 0);
  }
  for (int i = 0; i < n; i++) {
    cin >> c[i];
  }
  sa.topological_sort();
  vector<int64_t> pts(sa.size(), 0);
  for (int i = 0; i < n; i++) {
    int v = 0;
    for (int j = 0; j < s[i].size(); j++) {
      v = sa[v].next[s[i][j]];
      pts[v] += c[i];
    }
  }
  for (int i = sa.size() - 1; i > 0; i--) {
    pts[sa[i].link] += pts[i];
  }
  int64_t res = 0;
  for (int i = 1; i < sa.size(); i++) {
    res = max(res, pts[i] * sa[i].len);
  }
  cout << res << endl;
}