Given n strings Ai, Each string has a non-negative cost Ci.

Let’s define the function of string 
s: f(s)=∑ni=1Ci?tot(s,i)f(s)=∑i=1nCi?tot(s,i)

tot(s,i)      represents the number of occurrences of s in Ai

Find the maximal value of function f(s) over all strings.

Note that s is not necessary to be some string from A, and its length must be greater than zero.

Input

The first line is n (n≤105), denoting the number of strings，containing only a to z.

Then n lines each line is a string Ai.

Then a line contains n integers Ci.

The sum of length of all the string will no more than 105

Ci≤10000

Output

Output one line representing the maximal value.

Sample input and output

3
abc
abcd
cdab
1 2 3

6

Hint

Let S be ab, then the value will be 66, it’s the maximal value.

Source

My Solution

在队友帮忙debug的情况下，自己还是只Accepted了一个题目(┬＿┬)

字母也可以是字符串 s

在读入的时候统计好每个字符串中每个字母出现的个数  str[maxn][26]，然后读入权值以后forfor求出最大值，O(26n)  , 26 * 10^5次不会超时

然后 读入再用strlen()然后记录每个字母在每个字符串出现的次数才过了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;
const int maxn = 100000+8;
int str[maxn][26], c[maxn];
char ch[maxn];

int main()
{
    //freopen("a.txt","r",stdin);
    int n, len;
    long long sum = -1,tsum = 0;
    memset(str, 0, sizeof str);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%s", ch);
        len = strlen(ch);
        for(int j = 0; j < len; j++)
            str[i][ch[j] - 'a']++;
    /*    while(true){
            ch=getchar();
            if(isalpha(ch)==0) break;
            str[i][ch - 'a']++;
        }
    */
    }
    for(int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    for(int i = 0; i < 26; i++){
        tsum = 0;
        for(int j = 1; j <= n; j++){
            tsum += str[j][i]*c[j];
        }
        sum = max(sum, tsum);
    }
    printf("%lld", sum);
    return 0;
}