What joy! Petya's parents went on a business trip for the whole year and the playful kid is left all by himself. Petya got absolutely happy. He jumped on the bed and threw pillows all day long, until... 

Today Petya opened the cupboard and found a scary note there. His parents had left him with duties: he should water their favourite flower all year, each day, in the morning, in the afternoon and in the evening. "Wait a second!" — thought Petya. He know for a fact that if he fulfills the parents' task in the i-th (1 ≤ i ≤ 12) month of the year, then the flower will grow by ai centimeters, and if he doesn't water the flower in the i-th month, then the flower won't grow this month. Petya also knows that try as he might, his parents won't believe that he has been watering the flower if it grows strictly less than by k centimeters. 

Help Petya choose the minimum number of months when he will water the flower, given that the flower should grow no less than by k centimeters.

Input

The first line contains exactly one integer k (0 ≤ k ≤ 100). The next line contains twelve space-separated integers: the i-th (1 ≤ i ≤ 12) number in the line represents ai (0 ≤ ai ≤ 100). 

Output

Print the only integer — the minimum number of months when Petya has to water the flower so that the flower grows no less than by k centimeters. If the flower can't grow by k centimeters in a year, print -1.

Examples

Input

5
1 1 1 1 2 2 3 2 2 1 1 1


Output

2


Input

0
0 0 0 0 0 0 0 1 1 2 3 0


Output

0


Input

11
1 1 4 1 1 5 1 1 4 1 1 1


Output

3

Note

Let's consider the first sample test. There it is enough to water the flower during the seventh and the ninth month. Then the flower grows by exactly five centimeters.

In the second sample Petya's parents will believe him even if the flower doesn't grow at all (k = 0). So, it is possible for Petya not to water the flower at all.
import java.io.*;
import java.math.*;
import java.util.*;


public class Main {
    public static int ONLINE_MODE = 1;
    public static int OFFLINE_MODE = 2;

    public int mode = 0;

    public Scanner in = null;
    public BufferedWriter out = null;

    public Main(int mode, Scanner in, BufferedWriter out) {
        this.mode = mode;
        this.in = in;
        this.out = out;
    }

    public void open() {
        if (mode == Main.ONLINE_MODE) {
            in = new Scanner(System.in);
            out = new BufferedWriter(new OutputStreamWriter(System.out));
        }
    }

    public void close() {
        in.close();
        try {
            out.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public void echo(String output) {
        try {
            out.write(output);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public void echos(Collection collection, String separator) {
        StringBuffer sb = new StringBuffer();
        for (Object sentence : collection) {
            sb.append(sentence.toString() + separator);
        }
        String output = sb.toString().length() > 0 ?
                sb.toString().substring(0, sb.toString().length() - separator.length()) : sb.toString();
        echo(output);
    }

    public void echo(String format, Object... args) {
        String output = String.format(format, args);
        try {
            out.write(output);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        Main main = new Main(Main.ONLINE_MODE, null, null);
        main.open();
        main.execute();
        main.close();
    }

    // 工具方法

    public static int up(double num) {
        return (int) Math.ceil(num);
    }

    public static ArrayList<Character> chars(String word) {
        ArrayList<Character> chars = new ArrayList<Character>();
        for (char letter : word.toCharArray()) {
            chars.add(letter);
        }
        return chars;
    }

    // 临时区

    // 主程序

    public void execute() {
        int N = in.nextInt();
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < 12; i++) {
            int a = in.nextInt();
            list.add(a);
        }
        Collections.sort(list, Collections.reverseOrder());
        int total = N;
        int i;
        for (i = 0; i < 12; i++) {
            if (total <= 0)
                break;
            total -= list.get(i);
        }
        echo("%d%n", i == 12 && total != 0 ? -1 : i);
    }
}

class BI {
    public BigInteger bi;

    public BI(String value) {
        this.bi = new BigInteger(value);
    }

    public BI(BigInteger bi) {
        this.bi = bi;
    }

    public BI a(BI that) {
        return new BI(this.bi.add(that.bi));
    }

    public BI s(BI that) {
        return new BI(this.bi.subtract(that.bi));
    }

    public BI m(BI that) {
        return new BI(this.bi.multiply(that.bi));
    }

    public BI d(BI that) {
        return new BI(this.bi.divide(that.bi));
    }

    public BI r(BI that) {
        return new BI(this.bi.remainder(that.bi));
    }

    public int compareTo(BI that) {
        return this.bi.compareTo(that.bi);
    }

    public boolean g(BI that) {
        return this.bi.compareTo(that.bi) > 0;
    }

    public boolean ge(BI that) {
        return this.bi.compareTo(that.bi) >= 0;
    }

    public boolean l(BI that) {
        return this.bi.compareTo(that.bi) < 0;
    }

    public boolean le(BI that) {
        return this.bi.compareTo(that.bi) <= 0;
    }

    public BI a(int number) {
        return a(BI.v(number));
    }

    public BI s(int number) {
        return s(BI.v(number));
    }

    public BI m(int number) {
        return m(BI.v(number));
    }

    public BI d(int number) {
        return d(BI.v(number));
    }

    public BI r(int number) {
        return r(BI.v(number));
    }

    public int compareTo(int number) {
        return this.bi.compareTo(BI.v(number).bi);
    }

    public boolean g(int number) {
        return this.bi.compareTo(BI.v(number).bi) > 0;
    }

    public boolean ge(int number) {
        return this.bi.compareTo(BI.v(number).bi) >= 0;
    }

    public boolean l(int number) {
        return this.bi.compareTo(BI.v(number).bi) < 0;
    }

    public boolean le(int number) {
        return this.bi.compareTo(BI.v(number).bi) <= 0;
    }

    public static BI v(int number) {
        return new BI("" + number);
    }

    public String toString() {
        return this.bi + "";
    }
}