You are given a string of length n. Each character is one of the first p lowercase Latin letters.

You are also given a matrix A with binary values of size p × p. This matrix is symmetric (A_{ij} = A_{ji}). A_{ij} = 1 means that the string can have the i-th and j-th letters of Latin alphabet adjacent.

Let's call the string crisp if all of the adjacent characters in it can be adjacent (have 1 in the corresponding cell of matrix A).

You are allowed to do the following move. Choose any letter, remove all its occurrences and join the remaining parts of the string without changing their order. For example, removing letter 'a' from "abacaba" will yield "bcb".

The string you are given is crisp. The string should remain crisp after every move you make.

You are allowed to do arbitrary number of moves (possible zero). What is the shortest resulting string you can obtain?

Input

The first line contains two integers n and p (1 ≤ n ≤ 10^5, 1 ≤ p ≤ 17) — the length of the initial string and the length of the allowed prefix of Latin alphabet.

The second line contains the initial string. It is guaranteed that it contains only first p lowercase Latin letters and that is it crisp. Some of these p first Latin letters might not be present in the string.

Each of the next p lines contains p integer numbers — the matrix A (0 ≤ A_{ij} ≤ 1, A_{ij} = A_{ji}). A_{ij} = 1 means that the string can have the i-th and j-th letters of Latin alphabet adjacent.

Output

Print a single integer — the length of the shortest string after you make arbitrary number of moves (possible zero).

Examples

Input


7 3
abacaba
0 1 1
1 0 0
1 0 0


Output


7


Input


7 3
abacaba
1 1 1
1 0 0
1 0 0


Output


0


Input


7 4
bacadab
0 1 1 1
1 0 0 0
1 0 0 0
1 0 0 0


Output


5


Input


3 3
cbc
0 0 0
0 0 1
0 1 0


Output


0

Note

In the first example no letter can be removed from the initial string.

In the second example you can remove letters in order: 'b', 'c', 'a'. The strings on the intermediate steps will be: "abacaba" → "aacaa" → "aaaa" → "".

In the third example you can remove letter 'b' and that's it.

In the fourth example you can remove letters in order 'c', 'b', but not in the order 'b', 'c' because two letters 'c' can't be adjacent.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author prakharjain
 */
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);
        FCrispString solver = new FCrispString();
        solver.solve(1, in, out);
        out.close();
    }

    static class FCrispString {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();

            int p = in.nextInt();

            String s = in.next();

            int[] pos = new int[p];

            for (int i = 0; i < p; i++) {
                for (int j = 0; j < p; j++) {
                    if (in.nextInt() == 1)
                        pos[i] |= (1 << j);
                }
            }

            int[] h = new int[p];

            for (char c : s.toCharArray()) {
                h[c - 'a']++;
            }

            int[][] lc = new int[n][p];
            int[][] rc = new int[n][p];

            int[] temp = new int[p];
            Arrays.fill(temp, -1);
            for (int i = 0; i < n; i++) {
                char ch = s.charAt(i);
                int chi = ch - 'a';

                for (int j = 0; j < p; j++) {
                    lc[i][j] = temp[j];
                }

                temp[chi] = i;
            }

            Arrays.fill(temp, n);
            for (int i = n - 1; i >= 0; i--) {
                char ch = s.charAt(i);
                int chi = ch - 'a';

                for (int j = 0; j < p; j++) {
                    rc[i][j] = temp[j];
                }

                temp[chi] = i;
            }

            int[][] reach = new int[p][1 << p];

            int max = (1 << p) - 1;
            for (int i = 0; i < n; i++) {
                char ch = s.charAt(i);

                int ind = 0;
                int ci = i;
                char cc = ch;
                while (ind < max && ci >= 0) {
                    int cmax = -1;
                    for (int j = 0; j < p; j++) {
//                    if (j == ch - 'a')
//                        continue;
                        if ((ind & ((1 << j))) == 0 && lc[ci][j] > cmax) {
                            cmax = Math.max(cmax, lc[ci][j]);
                        }
                    }
                    if (cmax != -1 && s.charAt(cmax) != ch) {
                        if (ci != i)
                            ind |= (1 << (cc - 'a'));
                        ci = cmax;
                        cc = s.charAt(ci);
                        reach[ch - 'a'][ind] |= (1 << (cc - 'a'));
                    } else {
                        break;
                    }
                }

                ind = 0;
                ci = i;
                cc = ch;
                while (ind < max && ci < n) {
                    int cmax = n;
                    for (int j = 0; j < p; j++) {
//                    if (j == ch - 'a')
//                        continue;
                        if ((ind & ((1 << j))) == 0 && rc[ci][j] < cmax) {
                            cmax = Math.min(cmax, rc[ci][j]);
                        }
                    }
                    if (cmax != n) {
                        if (ci != i)
                            ind |= (1 << (cc - 'a'));
                        ci = cmax;
                        cc = s.charAt(ci);
                        reach[ch - 'a'][ind] |= (1 << (cc - 'a'));
                    } else {
                        break;
                    }
                }
            }

            for (int i = 0; i < p; i++) {
                for (int j = 0; j < p; j++) {
                    for (int mask = 0; mask < (1 << p); mask++) {
                        if ((mask & (1 << j)) != 0) {
                            reach[i][mask] |= reach[i][mask ^ (1 << j)];
                        }
                    }
                }
            }

            for (int i = 0; i < p; i++) {
                for (int mask = 0; mask < (1 << p); mask++) {
                    if ((mask & (1 << i)) != 0) {
                        reach[i][mask] = 0;
                        continue;
                    }
                    int val = reach[i][mask];

                    int and = val & mask;

                    reach[i][mask] ^= and;
                }
            }

            boolean[] br = new boolean[1 << p];

            Arrays.fill(br, true);

            for (int i = 0; i < p; i++) {
                for (int mask = 0; mask < (1 << p); mask++) {
                    if ((mask & (1 << i)) != 0) {
                        reach[i][mask] = 0;
                        continue;
                    }
                    int val = reach[i][mask];

                    for (int j = 0; j < p; j++) {
                        if ((val & (1 << j)) != 0) {
                            if ((pos[i] & (1 << j)) == 0) {
                                br[mask] = false;
                            }
                        }
                    }
                }
            }

            boolean[] dp = new boolean[1 << p];

            dp[0] = true;

            for (int mask = 1; mask < (1 << p); mask++) {
                for (int i = 0; i < p; i++) {
                    if ((mask & (1 << i)) != 0) {
                        if (dp[mask ^ (1 << i)] && br[mask]) {
                            dp[mask] = true;
                        }
                    }
                }
            }

            int ans = n;

            for (int mask = 1; mask < (1 << p); mask++) {
                if (dp[mask]) {
                    int ca = n;
                    for (int i = 0; i < p; i++) {
                        if ((mask & (1 << i)) != 0) {
                            ca -= h[i];
                        }
                    }

                    ans = Math.min(ans, ca);
                }
            }

            out.print(ans);
        }

    }

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

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

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

        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 String nextString() {
            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 String next() {
            return nextString();
        }

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

        }

    }

    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 print(int i) {
            writer.print(i);
        }

    }
}

