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;
struct debug_t {
  template <typename T>
  debug_t& operator<<(const T& obj) {
    return *this;
  }
  debug_t& write(const char data[], size_t n) { return *this; }
} debug;
struct Node;
vector<Node> nodes;
int prices[(int)1e5];
struct Node {
  int len;
  int firstPos;
  bool reachable;
  bool isClone = false;
  bool isSeparator = false;
  Node* link;
  Node* next[26] = {};
  vector<Node*> invLinks;
  int id;
  long long score = LLONG_MIN;
  Node() : len(0), reachable(true), link(nullptr) {}
  explicit Node(int len) : len(len), reachable(false) {}
  Node* Append(int c, Node* node) {
    assert(c >= 0 && c < 26);
    nodes.emplace_back(node->len + 1);
    auto cur = &nodes.back();
    cur->firstPos = node->len;
    for (; node && !node->next[c]; node = node->link) {
      node->next[c] = cur;
      cur->reachable = cur->reachable || node->reachable;
    }
    if (!node) {
      cur->link = this;
      return cur;
    }
    auto q = node->next[c];
    if (q->len == node->len + 1) {
      cur->link = q;
      return cur;
    }
    nodes.push_back(*q);
    auto clone = &nodes.back();
    clone->isClone = true;
    clone->len = node->len + 1;
    cur->link = q->link = clone;
    for (; node && node->next[c] == q; node = node->link) {
      node->next[c] = clone;
      clone->reachable = clone->reachable || node->reachable;
    }
    return cur;
  }
  long long GetScore() {
    if (score != LLONG_MIN) return score;
    assert(!isSeparator);
    score = isClone ? 0 : prices[id];
    for (auto node : invLinks) score += node->GetScore();
    assert(score != LLONG_MIN);
    return score;
  }
};
int offset[(int)1e5];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  nodes.reserve(int(1e6 + 1e5));
  int i, n;
  string s;
  while (cin >> n) {
    nodes.clear();
    Node root;
    auto node = &root;
    for (i = 0; i < n; i++) {
      offset[i] = node->len;
      cin >> s;
      for (char c : s) {
        node = root.Append(c - 'a', node);
        node->id = i;
      }
      nodes.emplace_back(node->len + 1);
      node = &nodes.back();
      node->link = &root;
      node->isSeparator = true;
    }
    for (i = 0; i < n; i++) cin >> prices[i];
    for (auto& node : nodes) node.link->invLinks.push_back(&node);
    long long result = 0;
    int resLen = 0;
    for (auto& node : nodes)
      if (!node.isSeparator && node.reachable) {
        int actualLen = min(node.len, node.firstPos - offset[node.id] + 1);
        assert(actualLen > 0);
        long long t = node.GetScore() * actualLen;
        if (t > result) {
          result = t;
          resLen = actualLen;
        }
      }
    cout << result;
    debug << ' ' << resLen;
    cout << '\n';
  }
}