Problem: Barney was hanging out with Nora for a while and now he thinks he may have feelings for her. Barney wants to send her a cheesy text message and wants to make her as happy as possible.

<image>

Initially, happiness level of Nora is 0. Nora loves some pickup lines like "I'm falling for you" and stuff. Totally, she knows n pickup lines, each consisting only of lowercase English letters, also some of them may be equal (in writing, but different in pronouncing or meaning though). Every time Nora sees i-th pickup line as a consecutive subsequence of Barney's text message her happiness level increases by ai. These substrings may overlap, for example, Nora will see the pickup line aa twice and the pickup line ab once in text message aaab.

Due to texting app limits, Barney's text may have up to l characters.

Barney asked you to help him make Nora as much happy as possible, it's gonna be legen...

Input

The first line of input contains two integers n and l (1 ≤ n ≤ 200, 1 ≤ l ≤ 1014) — the number of pickup lines and the maximum length of Barney's text.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 100), meaning that Nora's happiness level increases by ai after every time seeing i-th pickup line.

The next n lines contain the pickup lines. i-th of them contains a single string si consisting of only English lowercase letter. Summary length of all pickup lines does not exceed 200.

All strings are not empty.

Output

Print the only integer — the maximum possible value of Nora's happiness level after reading Barney's text.

Examples

Input

3 6
3 2 1
heart
earth
art


Output

6


Input

3 6
3 2 8
heart
earth
art


Output

16

Note

An optimal answer for the first sample case is hearth containing each pickup line exactly once.

An optimal answer for the second sample case is artart.

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Deque;
import java.util.ArrayList;
import java.io.OutputStreamWriter;
import java.io.OutputStream;
import java.util.Collection;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.util.List;
import java.io.Closeable;
import java.io.Writer;
import java.util.ArrayDeque;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            DLegen solver = new DLegen();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class DLegen {
        long inf = (long) 1e18;
        int m;

        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.readInt();
            long l = in.readLong();
            int[] a = new int[n];
            in.populate(a);

            char[][] s = new char[n][];
            for (int i = 0; i < n; i++) {
                s[i] = in.readString().toCharArray();
            }

            ACAutomaton ac = new ACAutomaton('a', 'z');
            for (int i = 0; i < n; i++) {
                ac.beginBuilding();
                for (char c : s[i]) {
                    ac.build(c);
                }
                ac.getBuildLast().increaseCnt(a[i]);
            }
            ac.endBuilding();
            ACAutomaton.Node[] nodes = ac.getAllNodes().toArray(new ACAutomaton.Node[0]);
            m = nodes.length;
            long[][] mat = new long[m][m];
            SequenceUtils.deepFill(mat, -inf);
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < 'z' - 'a' + 1; j++) {
                    mat[i][nodes[i].next[j].id] = nodes[i].next[j].getPreSum();
                }
            }

            long ans = 0;
            long[][] trans = pow(mat, l);
            for (int i = 0; i < m; i++) {
                ans = Math.max(ans, trans[0][i]);
            }

            out.println(ans);
        }

        public long[][] mul(long[][] a, long[][] b) {
            long[][] ans = new long[m][m];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < m; j++) {
                    long x = -inf;
                    for (int k = 0; k < m; k++) {
                        x = Math.max(x, a[i][k] + b[k][j]);
                    }
                    ans[i][j] = x;
                }
            }
            return ans;
        }

        public long[][] pow(long[][] x, long n) {
            if (n == 0) {
                long[][] ans = new long[m][m];
                SequenceUtils.deepFill(ans, -inf);
                for (int i = 0; i < m; i++) {
                    ans[i][i] = 0;
                }
                return ans;
            }
            long[][] ans = pow(x, n / 2);
            ans = mul(ans, ans);
            if (n % 2 == 1) {
                ans = mul(ans, x);
            }
            return ans;
        }

    }

    static class ACAutomaton {
        private final int minCharacter;
        private final int maxCharacter;
        private final int range;
        private ACAutomaton.Node root;
        private ACAutomaton.Node buildLast;
        private List<ACAutomaton.Node> allNodes = new ArrayList();

        public ACAutomaton.Node getBuildLast() {
            return buildLast;
        }

        public List<ACAutomaton.Node> getAllNodes() {
            return allNodes;
        }

        private ACAutomaton.Node addNode() {
            ACAutomaton.Node node = new ACAutomaton.Node(range);
            node.id = allNodes.size();
            allNodes.add(node);
            return node;
        }

        public ACAutomaton(int minCharacter, int maxCharacter) {
            this.minCharacter = minCharacter;
            this.maxCharacter = maxCharacter;
            range = maxCharacter - minCharacter + 1;
            root = addNode();
        }

        public void beginBuilding() {
            buildLast = root;
        }

        public void endBuilding() {
            //treeOrder = new ArrayList<>(allNodes.size());
            //treeOrder.add(root);
            Deque<ACAutomaton.Node> deque = new ArrayDeque(allNodes.size());
            for (int i = 0; i < range; i++) {
                if (root.next[i] != null) {
                    deque.addLast(root.next[i]);
                }
            }

            while (!deque.isEmpty()) {
                ACAutomaton.Node head = deque.removeFirst();
                //treeOrder.add(head);
                ACAutomaton.Node fail = visit(head.father.fail, head.index);
                if (fail == null) {
                    head.fail = root;
                } else {
                    head.fail = fail.next[head.index];
                }
                head.preSum = head.cnt + head.fail.preSum;
                for (int i = 0; i < range; i++) {
                    if (head.next[i] != null) {
                        deque.addLast(head.next[i]);
                    }
                }
            }

            for (int i = 0; i < range; i++) {
                if (root.next[i] != null) {
                    deque.addLast(root.next[i]);
                } else {
                    root.next[i] = root;
                }
            }
            while (!deque.isEmpty()) {
                ACAutomaton.Node head = deque.removeFirst();
                for (int i = 0; i < range; i++) {
                    if (head.next[i] != null) {
                        deque.addLast(head.next[i]);
                    } else {
                        head.next[i] = head.fail.next[i];
                    }
                }
            }
        }

        public ACAutomaton.Node visit(ACAutomaton.Node trace, int index) {
            while (trace != null && trace.next[index] == null) {
                trace = trace.fail;
            }
            return trace;
        }

        public void build(char c) {
            int index = c - minCharacter;
            if (buildLast.next[index] == null) {
                ACAutomaton.Node node = addNode();
                node.father = buildLast;
                node.index = index;
                buildLast.next[index] = node;
            }
            buildLast = buildLast.next[index];
        }

        public static class Node {
            public ACAutomaton.Node[] next;
            ACAutomaton.Node fail;
            ACAutomaton.Node father;
            int index;
            public int id;
            int cnt;
            int preSum;

            public void increaseCnt(int k) {
                cnt += k;
            }

            public int getPreSum() {
                return preSum;
            }

            public Node(int range) {
                next = new ACAutomaton.Node[range];
            }

            public String toString() {
                return father == null ? "" : (father.toString() + (char) ('a' + index));
            }

        }

    }

    static class SequenceUtils {
        public static void deepFill(Object array, long val) {
            if (!array.getClass().isArray()) {
                throw new IllegalArgumentException();
            }
            if (array instanceof long[]) {
                long[] longArray = (long[]) array;
                Arrays.fill(longArray, val);
            } else {
                Object[] objArray = (Object[]) array;
                for (Object obj : objArray) {
                    deepFill(obj, val);
                }
            }
        }

    }

    static class FastInput {
        private final InputStream is;
        private StringBuilder defaultStringBuf = new StringBuilder(1 << 13);
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        public void populate(int[] data) {
            for (int i = 0; i < data.length; i++) {
                data[i] = readInt();
            }
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public long readLong() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            long val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public String readString(StringBuilder builder) {
            skipBlank();

            while (next > 32) {
                builder.append((char) next);
                next = read();
            }

            return builder.toString();
        }

        public String readString() {
            defaultStringBuf.setLength(0);
            return readString(defaultStringBuf);
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private StringBuilder cache = new StringBuilder(10 << 20);
        private final Writer os;

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            return this;
        }

        public FastOutput append(long c) {
            cache.append(c);
            return this;
        }

        public FastOutput println(long c) {
            return append(c).println();
        }

        public FastOutput println() {
            cache.append(System.lineSeparator());
            return this;
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }
}