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.util.*;
import java.io.*;
public class F
{
	public static int[][] rank;
	public static int[] sa;
	public static int[] lcp;
	
	public static void main(String[] args) throws Exception
	{
		FastScanner in = new FastScanner(System.in);
		
		int n = in.nextInt();
		
		StringBuilder sb = new StringBuilder();
		ArrayList<Integer> starts = new ArrayList<Integer>();
		for(int x = 0; x < n; x++)
		{
			starts.add(sb.length());
			sb.append(in.next());
			sb.append('#');
		}
		
		starts.add(sb.length());
		
		int[] cost = new int[n];
		for(int y = 0; y < n; y++)
		{
			cost[y] = in.nextInt();
		}
		
		createSuffixArray(sb.toString());
		
		long[] value = new long[sb.length()];
		long[] dist = new long[sb.length()];
		for(int z = 0; z < starts.size() - 1; z++)
		{
			for(int a = starts.get(z); a < starts.get(z + 1); a++)
			{
				value[a] = cost[z];
				dist[a] = starts.get(z + 1) - 1 - a;
			}
		}
		
		DisjointSet ds = new DisjointSet(sb.length(), value);
		
		LCP[] lcps = new LCP[lcp.length];
		for(int b = 0; b < lcp.length; b++)
		{
			lcps[b] = new LCP(lcp[b], b);
		}
		
		Arrays.sort(lcps);
		
		long result = Long.MIN_VALUE;
		for(int c = 0; c < sa.length; c++)
		{
			if((c == 0 || dist[sa[c]] > lcp[c - 1]) && (c == sa.length - 1 || dist[sa[c]] > lcp[c]))
			{
				result = Math.max(result, dist[sa[c]] * value[sa[c]]);
			}
		}
		
		for(int d = 0; d < lcps.length; d++)
		{
			int index = d;
			while(index < lcps.length && lcps[d].val == lcps[index].val)
			{
				ds.union(sa[lcps[index].index], sa[lcps[index].index + 1]);
				index++;
			}
			
			for(int e = d; e < index; e++)
			{
				result = Math.max(result, ds.value[ds.find(sa[lcps[e].index])] * lcps[e].val);
			}
			
			d = index - 1;
		}
		
		System.out.println(result);
	}
	
	public static void createSuffixArray(String s)
	{
		int n = s.length();
		
		int steps = 0;
		while((1 << steps) <= n)
		{
			steps++;
		}
		
		rank = new int[steps + 1][n];
		
		for(int i = 0; i < s.length(); i++)
		{
			if(s.charAt(i) == '#')
			{
				rank[0][i] = 26 + i;
			}
			else
			{
				rank[0][i] = s.charAt(i) - 'a';
			}
		}
		
		for(int j = 1; j < rank.length; j++)
		{
			long[] suffixes = new long[n];
			for(int k = 0; k < s.length(); k++)
			{
				if(k + (1 << (j - 1)) < s.length())
				{
					suffixes[k] = ((long)rank[j - 1][k] << 40L) + ((long)(rank[j - 1][k + (1 << (j - 1))] + 1) << 20L) + k;
				}
				else
				{
					suffixes[k] = ((long)rank[j - 1][k] << 40L) + k;
				}
			}
			
			Arrays.sort(suffixes);
			
			for(int k = 0; k < s.length(); k++)
			{
				if(k > 0 && suffixes[k] / (1L << 20) == suffixes[k - 1] / (1L << 20))
				{
					rank[j][(int)(suffixes[k] % (1L << 20))] = rank[j][(int)(suffixes[k - 1] % (1L << 20))];
				}
				else
				{
					rank[j][(int)(suffixes[k] % (1L << 20))] = k;
				}
			}
		}
		
		sa = new int[n];
		for(int i = 0; i < rank[0].length; i++)
		{
			sa[rank[rank.length - 1][i]] = i;
		}
		
		lcp = new int[n - 1];
		for(int i = 0; i < sa.length - 1; i++)
		{
			lcp[i] = lcp(sa[i], sa[i + 1]);
		}
	}
	
	public static int lcp(int a, int b)
	{
		if(a == b)
		{
			return sa.length - a;
		}
		else
		{
			int ret = 0;
			for(int k = rank.length - 1; k >= 0 && a < sa.length && b < sa.length; k--)
			{
				if(rank[k][a] == rank[k][b])
				{
					a += 1 << k;
					b += 1 << k;
					ret += 1 << k;
				}
			}
			
			return ret;
		}
	}
	
	static class LCP implements Comparable<LCP>
	{
		int val;
		int index;
		
		public LCP(int v, int i)
		{
			val = v;
			index = i;
		}
		
		public int compareTo(LCP o)
		{
			return o.val - val;
		}
	}
	
	static class DisjointSet
	{
		int[] parent;
		int[] rank;
		long[] value;
		
		public DisjointSet(int n, long[] v)
		{
			parent = new int[n];
			rank = new int[n];
			value = v;
			
			for(int i = 0; i < parent.length; i++)
			{
				parent[i] = i;
			}
		}
		
		public int find(int x)
		{
			if(parent[x] != x)
			{
				parent[x] = find(parent[x]);
			}
			
			return parent[x];
		}
		
		public boolean union(int x, int y)
		{
			int a = find(x);
			int b = find(y);
			
			if(a == b)
			{
				return false;
			}
			else
			{
				if(rank[a] < rank[b])
				{
					parent[a] = b;
					value[b] += value[a];
				}
				else if(rank[a] > rank[b])
				{
					parent[b] = a;
					value[a] += value[b];
				}
				else
				{
					parent[b] = a;
					rank[a]++;
					value[a] += value[b];
				}
				
				return true;
			}
		}
	}
	
	static class FastScanner
	{
		BufferedReader br;
		StringTokenizer st;
		
		public FastScanner(InputStream input)
		{
			br = new BufferedReader(new InputStreamReader(input));
			st = new StringTokenizer("");
		}
		
		public String next() throws IOException
		{
			if(st.hasMoreTokens())
			{
				return st.nextToken();
			}
			else
			{
				st = new StringTokenizer(br.readLine());
				return next();
			}
		}
		
		public int nextInt() throws IOException
		{
			return Integer.parseInt(next());
		}
	}
}