Sasha and Kolya decided to get drunk with Coke, again. This time they have k types of Coke. i-th type is characterised by its carbon dioxide concentration <image>. Today, on the party in honour of Sergiy of Vancouver they decided to prepare a glass of Coke with carbon dioxide concentration <image>. The drink should also be tasty, so the glass can contain only integer number of liters of each Coke type (some types can be not presented in the glass). Also, they want to minimize the total volume of Coke in the glass.

Carbon dioxide concentration is defined as the volume of carbone dioxide in the Coke divided by the total volume of Coke. When you mix two Cokes, the volume of carbon dioxide sums up, and the total volume of Coke sums up as well.

Help them, find the minimal natural number of liters needed to create a glass with carbon dioxide concentration <image>. Assume that the friends have unlimited amount of each Coke type.

Input

The first line contains two integers n, k (0 ≤ n ≤ 1000, 1 ≤ k ≤ 106) — carbon dioxide concentration the friends want and the number of Coke types.

The second line contains k integers a1, a2, ..., ak (0 ≤ ai ≤ 1000) — carbon dioxide concentration of each type of Coke. Some Coke types can have same concentration.

Output

Print the minimal natural number of liter needed to prepare a glass with carbon dioxide concentration <image>, or -1 if it is impossible.

Examples

Input

400 4
100 300 450 500


Output

2


Input

50 2
100 25


Output

3

Note

In the first sample case, we can achieve concentration <image> using one liter of Coke of types <image> and <image>: <image>.

In the second case, we can achieve concentration <image> using two liters of <image> type and one liter of <image> type: <image>.
import java.io.*;
import java.util.*;
import java.util.function.Consumer;

public class Main {
    static MyScanner sc;
    private static PrintWriter out;
    static long M2 = 1_000_000_000L + 7;

    public static void main(String[] s) throws Exception {
        StringBuilder stringBuilder = new StringBuilder();


//        stringBuilder.append("13 3\n" +
//                "1 2\n" +
//                "3 2\n" +
//                "4 2\n" +
//                "5 2\n" +
//                "3 6\n" +
//                "10 6\n" +
//                "6 7\n" +
//                "6 13\n" +
//                "5 8\n" +
//                "5 9\n" +
//                "9 11\n" +
//                "11 12");
        // 2 - 1 - 3
        //     4
        // 1 1 2 2 3
        // 1 1 2 2
        // 1 1 2
        // 1 1
        // 1
        if (stringBuilder.length() == 0) {
            sc = new MyScanner(System.in);
        } else {
            sc = new MyScanner(new BufferedReader(new StringReader(stringBuilder.toString())));
        }


        out = new PrintWriter(new OutputStreamWriter(System.out));
        initData();
        solve();
        out.flush();
    }


    private static void initData() {
    }

    private static void solve() throws IOException {
        int k = sc.nextInt();
        int n = sc.nextInt();
        boolean[] pos = new boolean[2001];

        ArrayList<Integer> n1 = new ArrayList<>();
        boolean [] hl = new boolean[2];
        for (int s = 0; s < n; s++) {
            int inp = sc.nextInt();
            inp += 1000 - k;
            if (pos[inp]) continue;
            pos[inp] = true;
            n1.add(inp);
        }


        n1.sort(Comparator.naturalOrder());
        int l = 1;
        ArrayList<Integer> lastA = new ArrayList<>(n1);

        while (!pos[1000] && lastA.size() >0) {
            ArrayList<Integer> next = new ArrayList<>();
            for (int i : lastA) {
                for (int j : n1) {
                    int nn = i + j - 1000;
                    if (nn < 0 || nn >= pos.length || pos[nn]) continue;
                    pos[nn] = true;
                    next.add(nn);
                }
            }
            lastA = next;
            l++;
        }
        out.println(pos[1000] ? l : -1);
    }

    private static boolean[] merge(boolean[] init, boolean[] data) {
        boolean[] rr = new boolean[init.length];
        for (int s = 0; s < init.length; s++) {
            for (int k = Math.max(0, 1000 - s); k < data.length; k++) {
                int ind = s + k - 1000;
                if (ind >= init.length) break;
                rr[ind] |= init[s] && data[k];
            }
        }
        return rr;
    }


    private static int[] dfs(int start, int[][] neig, Consumer<int[]> onAdd, Consumer<int[]> onRemove) {
        int[][] vis0 = new int[neig.length * 2][];
        int l = 0;
        vis0[l++] = new int[]{start, 0, -1, 0, 0};

        boolean[] vis = new boolean[neig.length];
        vis[start] = true;
        int[] level = new int[neig.length];
        while (l > 0) {
            int[] ppr = vis0[--l];
            if (ppr[1] == 1) {
                onRemove.accept(ppr);
                continue;
            }
            ppr[1] = 1;
            int i = ppr[0];
            vis0[l++] = ppr;
            onAdd.accept(ppr);
            for (int kk : neig[i]) {
                if (!vis[kk]) {
                    vis[kk] = true;
                    level[kk] = level[i] + 1;
                    vis0[l++] = new int[]{kk, 0, i, level[kk]};
                }
            }
        }
        return level;
    }

    private static int[][] tr(int n) {
        int[][] x = new int[2][n - 1];
        for (int i = 0; i < n - 1; i++) {
            x[0][i] = sc.nextInt() - 1;
            x[1][i] = sc.nextInt() - 1;
        }
        return pn(x, n);
    }

    private static int[][] pn(int[][] x, int n) {
        int[] ct = new int[n];
        int[][] res = new int[n][];
        for (int v : x[0]) {
            ct[v]++;
        }
        for (int v : x[1]) {
            ct[v]++;
        }
        for (int l = 0; l < n; l++) {
            res[l] = new int[ct[l]];
        }
        for (int i = 0; i < x[0].length; i++) {
            res[x[0][i]][--ct[x[0][i]]] = x[1][i];
            res[x[1][i]][--ct[x[1][i]]] = x[0][i];
        }
        return res;
    }


    private static void solveT() throws IOException {
        int t = sc.nextInt();
        while (t-- > 0) {
            solve();
        }
    }

    private static long gcd(long l, long l1) {
        if (l > l1) return gcd(l1, l);
        if (l == 0) return l1;
        return gcd(l1 % l, l);
    }

    private static long pow(long a, long b, long m) {
        if (b == 0) return 1;
        if (b == 1) return a;
        long pp = pow(a, b / 2, m);
        pp *= pp;
        pp %= m;
        return (pp * (b % 2 == 0 ? 1 : a)) % m;
    }


    static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        MyScanner(BufferedReader br) {
            this.br = br;
        }

        public MyScanner(InputStream in) {
            this(new BufferedReader(new InputStreamReader(in)));
        }

        void findToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
        }

        String next() {
            findToken();
            return st.nextToken();
        }

        Integer[] nab(int n) {
            Integer[] k = new Integer[n];
            for (int i = 0; i < n; i++) {
                k[i] = sc.fi();
            }
            return k;
        }

        int[] na(int n) {
            int[] k = new int[n];
            for (int i = 0; i < n; i++) {
                k[i] = sc.fi();
            }
            return k;
        }

        long[] nl(int n) {
            long[] k = new long[n];
            for (int i = 0; i < n; i++) {
                k[i] = sc.nextLong();
            }
            return k;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int fi() {
            String t = next();
            int cur = 0;
            boolean n = t.charAt(0) == '-';
            for (int a = n ? 1 : 0; a < t.length(); a++) {
                cur = cur * 10 + t.charAt(a) - '0';
            }
            return n ? -cur : cur;
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }


}