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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Junior Andrade
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskF solver = new TaskF();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskF {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();
            String[] s = IOUtils.readStringArray(in, n);
            long[] c = IOUtils.readLongArray(in, n);
            SuffixAutomata suff = new SuffixAutomata(500050);

            long[] pd = new long[1000050];
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < s[i].length(); ++j) {
                    int ch = s[i].charAt(j) - 'a';
                    suff.add(ch);
                    pd[suff.last] += c[i];
                }
                //out.printLine(suff.last);
                suff.setLast(0);
            }

            long ans = 0;
            ArrayList<Integer>[] arr = new ArrayList[suff.sz];
            for (int i = 0; i < suff.sz; ++i) arr[i] = new ArrayList<Integer>();
            for (int i = 1; i < suff.sz; ++i) arr[suff.st[i].len].add(i);
            for (int i = suff.sz - 1; i >= 0; --i) {
                for (int j = 0; j < arr[i].size(); ++j) {
                    int id = arr[i].get(j);
                    pd[suff.st[id].link] += pd[id];
                    //out.printLine("dp["+id+"] = " + pd[id]);
                    ans = Math.max(ans, pd[id] * suff.st[id].len);
                }
            }
            out.printLine(ans);

        }

    }

    static class SuffixAutomata {
        public state[] st;
        public int sz;
        public int last;
        private long differentStrings;
        private long uniqueSubstrings;
        private int size;

        public SuffixAutomata() {
            this.size = 100020;
            this.st = new state[this.size * 2];
            init();
        }

        public SuffixAutomata(int size) {
            this.size = size;
            this.st = new state[this.size * 2];
            init();
        }

        public void setLast(int x) {
            this.last = x;
        }

        public void init() {
            this.sz = 0;
            this.st[sz] = new state();
            this.st[sz].link = -1;
            this.last = 0;
            this.differentStrings = this.uniqueSubstrings = 0;
            sz++;
        }

        public void add(int c) {

            if (st[last].next[c] != 0) {
                int p = last;
                int q = st[p].next[c];
                if (st[q].len == st[p].len + 1) {
                    last = q;
                    return;
                }

                int clone = sz++;
                st[clone] = new state();
                st[clone].len = st[p].len + 1;
                for (int i = 0; i < 27; ++i) {
                    int v = st[q].next[i];
                    st[clone].next[i] = v;
                }
                st[clone].link = st[q].link;
                st[clone].isClone = true;
                //Atualização das transições c
                for (; p != -1 && st[p].next[c] == q; p = st[p].link) st[p].next[c] = clone;
                st[q].link = clone;
                last = clone;
                return;
            }

            int cur = sz++;
            st[cur] = new state();
            st[cur].len = st[last].len + 1;
            st[cur].qtd = 1;
            int p;
            for (p = last; p != -1 && st[p].next[c] == 0; p = st[p].link) st[p].next[c] = cur;
            if (p == -1) {
                // Não ocorreu trancição c nos estados terminais
                st[cur].link = 0;
            } else {
                //Ocorreu transição c no estado p
                int q = st[p].next[c];
                if (st[p].len + 1 == st[q].len) st[cur].link = q;
                else {
                    //Cria clone do vertice q
                    int clone = sz++;
                    st[clone] = new state();
                    st[clone].len = st[p].len + 1;
                    for (int i = 0; i < 27; ++i) {
                        int v = st[q].next[i];
                        st[clone].next[i] = v;
                    }
                    st[clone].link = st[q].link;
                    st[clone].isClone = true;
                    //Atualização das transições c
                    for (; p != -1 && st[p].next[c] == q; p = st[p].link) st[p].next[c] = clone;
                    st[q].link = st[cur].link = clone;
                }
            }

            differentStrings += (st[cur].len - st[st[cur].link].len);
            //Atualiza estado em que ocorre o texto
            last = cur;
        }

        static public class state {
            public int len;
            public int link;
            public int qtd;
            public int[] next;
            public boolean isClone;

            public state() {
                this.len = this.link = this.qtd = 0;
                this.isClone = false;
                this.next = new int[27];
            }

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void printLine(long i) {
            writer.println(i);
        }

    }

    static class IOUtils {
        public static long[] readLongArray(InputReader in, int size) {
            long[] array = new long[size];
            for (int i = 0; i < size; i++)
                array[i] = in.nextLong();
            return array;
        }

        public static String[] readStringArray(InputReader in, int size) {
            String[] array = new String[size];
            for (int i = 0; i < size; i++)
                array[i] = in.readString();
            return array;
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                if (Character.isValidCodePoint(c))
                    res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}