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 JAVA):

Solution:
import java.io.*;
import java.util.*;

public class F616{
	public static boolean DEBUG = true;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer st;

		int n = nextInt(br);

		StringBuilder sb = new StringBuilder();

		int[] locs = new int[n+1];
		int c = 0;

		for(int i = 0; i < n; i++){
			sb.append("%");
			String s = br.readLine();
			sb.append(s);

			locs[i] = c;
			c += s.length() + 1;
		}

		sb.append("$");

		c++;

		locs[n] = c-1;

		int[] vals = new int[n];
		st = getst(br);

		for(int i = 0; i < n; i++){
			vals[i] = nextInt(st);
		}

		int[][] s = suffixArray(sb.toString());

		int[] suffix = s[0];
		int[] lcp = s[1];

		long[] prefix = new long[c];

		for(int i = n+1; i < c; i++){
			int loc = -Arrays.binarySearch(locs, suffix[i]) - 2;

			prefix[i] = prefix[i-1] + vals[loc];
		}

		// debug(Arrays.toString(suffix));
		// debug(Arrays.toString(lcp));
		// debug(Arrays.toString(prefix));

		Stack<Pair> pq = new Stack<Pair>();
		pq.push(new Pair(-1, 0));

		long ans = 0;

		for(int i = n+1; i < c; i++){
			int lastStart = i;

			while(pq.peek().a > lcp[i]){
				Pair l = pq.pop();
				lastStart = l.b;
				// debug("String of length " + l.a + " had " + (i-l.b+1) + " substrings.");
				// debug((prefix[c-1] - prefix[l.b-2]) / 2l * (long)(l.a));
				ans = Math.max(ans, (prefix[i-1] - prefix[l.b-2]) * (long)(l.a));
			}

			int nextInd = -Arrays.binarySearch(locs, suffix[i]) - 1;
			long len = locs[nextInd] - suffix[i];

			if((i < c-1 && Math.max(lcp[i], lcp[i+1]) < len) || (i == c-1 && lcp[i] < len)){
				// debug("String of length " + len + " had 1 substring.");
				// debug(len * vals[nextInd-1]);
				ans = Math.max(ans, len * vals[nextInd-1]);
			}

			if(pq.peek().a < lcp[i]){
				pq.push(new Pair(lcp[i], lastStart));
			}
		}

		while(pq.size() > 1){
			Pair l = pq.pop();
			// debug("String of length " + l.a + " had " + (c-l.b+1) + " substrings.");
			// debug((prefix[c-1] - prefix[l.b-2]) / 2l * (long)(l.a));
			ans = Math.max(ans, (prefix[c-1] - prefix[l.b-2]) * (long)(l.a));
		}

		pw.println(ans);
		
		br.close();
		pw.close();
	}

	public static int[][] suffixArray(String s){ // O(n log^2 n)
		int m = 33 - Integer.numberOfLeadingZeros(s.length());
		int[][] sortIndex = new int[m][s.length()];

		for(int i = 0; i < s.length(); i++){
			sortIndex[0][i] = (s.charAt(i) == '%' ? -i : s.charAt(i));
		}

		for(int j = 1; j < m; j++){
			Triple[] l = new Triple[s.length()];

			for(int i = 0; i < s.length(); i++){
				l[i] = new Triple(sortIndex[j-1][i],
					(i + (1 << (j-1)) < s.length()
						? sortIndex[j-1][i + (1 << (j-1))]
						: -1),
					i);
			}

			Arrays.sort(l);

			for(int i = 0; i < s.length(); i++){
				sortIndex[j][l[i].c] = (i == 0 || l[i].compareTo(l[i-1]) != 0)
				? i
				: sortIndex[j][l[i-1].c];
			}
		}

		int[] order = new int[s.length()];

		for(int i = 0; i < s.length(); i++){
			order[sortIndex[m-1][i]] = i;
		}

		int[] lcp = new int[s.length()];

		for(int i = 1; i < s.length(); i++){
			int a = order[i-1];
			int b = order[i];
			for(int k = m-1; k >= 0; k--){
				if(sortIndex[k][a] == sortIndex[k][b]){
					lcp[i] += (1 << k);
					a += (1 << k);
					b += (1 << k);
				}
			}
		}

		int[][] ret = {order, lcp};

		return ret;
	}

	static class Pair implements Comparable<Pair> {
		int a;
		int b;

		public Pair(int ma, int mb){
			a = ma;
			b = mb;
		}

		public int compareTo(Pair o){
			return o.a - a;
		}
	}

	static class Triple implements Comparable<Triple> {
		int a;
		int b;
		int c;

		public Triple(int ma, int mb, int mc){
			a = ma;
			b = mb;
			c = mc;
		}

		public int compareTo(Triple o){
			if(a == o.a){
				return b - o.b;
			} else {
				return a - o.a;
			}
		}
	}
	
	public static void debug(Object o){
		if(DEBUG){
			System.out.println("~" + o);
		}
	}
	
	public static StringTokenizer getst(BufferedReader br) throws Exception{
		return new StringTokenizer(br.readLine(), " ");
	}
	
	public static int nextInt(BufferedReader br) throws Exception{
		return Integer.parseInt(br.readLine());
	}
	
	public static int nextInt(StringTokenizer st) throws Exception{
		return Integer.parseInt(st.nextToken());
	}
	
	public static long nextLong(BufferedReader br) throws Exception{
		return Long.parseLong(br.readLine());
	}
	
	public static long nextLong(StringTokenizer st) throws Exception{
		return Long.parseLong(st.nextToken());
	}
	
	public static double nextDouble(BufferedReader br) throws Exception{
		return Double.parseDouble(br.readLine());
	}
	
	public static double nextDouble(StringTokenizer st) throws Exception{
		return Double.parseDouble(st.nextToken());
	}
}