跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F1415. Expensive Strings

  • ID: 1421
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:挑战
  • 上传者:
  • 数据结构
  • 排序
  • 后缀结构
  • 字符串
  • 编程与模拟
  • 挑战
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Expensive Strings

题目描述

F. Expensive Strings
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given n strings ti. Each string has cost ci.

Let's define the function of string , 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

题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 919 题。保留原作者与原赛事署名。