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.
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
//package javaapplication45;

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

/**
 *
 * @author Asad Abbas
 */
public class JavaApplication45 {

    /**
     * @param args the command line arguments
     */
    static int[] reverse(int [] arr , int s , int e){
        int temp = s;
        int [] newarray = new int[arr.length];
        for (int i = e; i >=s ; i--) {
            newarray[temp] = arr[i];
            temp++;
        }
        for (int i = 0; i < arr.length; i++) {
            if(newarray[i] == 0){
                newarray[i] = arr[i];
            }
        }
        return newarray;
    }
    static void p(String s){
        System.out.println(s + " ");
    }
    static void pr(List<Integer> m){
        for (int i = 0; i < m.size(); i++) {
            p(m.get(i)+"");
        }
    }
    static String Dis(String s){
        String d = "";
        List<String> arr = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if(arr.contains(s.charAt(i)+"")){
                
            }else{
                d = d + s.charAt(i);
                arr.add(s.charAt(i)+"");
                
            }
        }
        
        return d;
    }
    
   public static List<String> getsub(String ss){
       List<String> data = new ArrayList<>();
       for (int j = 1; j <=ss.length(); j++) {
            for (int i = 0; i < ss.length()-(j-1) ; i++) {
              data.add(ss.substring(i,(i + j)));
           }
        }
       return data;
   }
   static String[][] volleyballPositions(String[][] formation, int k) {
       int[][] pos = {{2, 1}, {3, 0}, {1, 0}, {0, 1}, {1, 2}, {3, 2}};
       String[][] res = new String[formation.length][];
       for (int i = 0; i < formation.length; i++) {
          res[i] = Arrays.copyOf(formation[i], formation[i].length);
       }
       for (int i = 0; i < 6; i++) {
         int i1 = pos[i][0];
         int j1 = pos[i][1];
       }
       return res;
}

    static boolean Isnumber(char a){
        char [] arr = {'0','1','2','3','4','5','6','7','8','9'};
        for (int i = 0; i < arr.length; i++) {
            if(a == arr[i]){
                return true;
            }
        }
        return false;
    }
    static boolean IsAlphabet(char a)
    {
       int ascii = a;
       if(ascii >= 65 && ascii <= 90){
           return true;
       }
       else if(ascii >=97 && ascii <= 122){
           return true;
       }
       return false;
    }
    static String passwordNormalization(String password) {
        String num = "";
        String Alpha = "";
        String Character = "";
        for (int i = 0; i < password.length(); i++) {
            char a = password.charAt(i);
            if(Isnumber(a)){
                num = num + (a+"");
            }
            else if(IsAlphabet(a)){
                Alpha = Alpha + (a+"");
            }
            else{
                Character = Character + (a+"");
            }
            
        }
        String ans = Alpha+num+Character;
        return ans;
    }

    static boolean Check(String a  , String b){
       
        String vowel = "aeiouy";
        if(a.equals(b)){
            return false;
        }
        else if(vowel.contains(a) && vowel.contains(b)){
            return false;
        }
        
        return true;
    }
    private static List<String> Get() {
       List<String> roman = new ArrayList<>();
       roman.add("I");
       roman.add("II");
       roman.add("III");
       roman.add("IV");
       roman.add("V");
       roman.add("VI");
       roman.add("VII");
       roman.add("VIII");
       roman.add("IX");
       roman.add("X");
       roman.add("XI");
       roman.add("XII");
       roman.add("XIII");
       roman.add("XIV");
       roman.add("XV");
       roman.add("XVI");
       roman.add("XVII");
       roman.add("XVIII");
       roman.add("XIX");
       roman.add("XX");
       roman.add("XXI");
       roman.add("XXII");
       roman.add("XXIII");
       roman.add("XXIV");
       roman.add("XXV");
       roman.add("XXVI");
       roman.add("XXVII");
       roman.add("XXVIII");
       roman.add("XXIX");
       roman.add("XXX");
       roman.add("XXXI");
       roman.add("XXXII");
       roman.add("XXXIII");
       roman.add("XXXIV");
       roman.add("XXXV");
       roman.add("XXXVI");
       roman.add("XXXVII");
       roman.add("XXXVIII");
       roman.add("XXXIX");
       roman.add("XL");
       roman.add("XLI");
       roman.add("XLII");
       roman.add("XLIII");
       roman.add("XLIV");
       roman.add("XLV");
       roman.add("XLVI");
       roman.add("XLVII");
       roman.add("XLVIII");
       roman.add("XLIX");
       roman.add("L");
       roman.add("LI");
       roman.add("LII");
       roman.add("LIII");
       roman.add("LIV");
       roman.add("LV");
       roman.add("LVI");
       roman.add("LVII");
       roman.add("LVIII");
       roman.add("LIX");
       roman.add("LX");
       roman.add("LXI");
       roman.add("LXII");
       roman.add("LXIII");
       roman.add("LXIV");
       roman.add("LXV");
       roman.add("LXVI");
       roman.add("LXVII");
       roman.add("LXVIII");
       roman.add("LXVIII");
       roman.add("LXIX");
       roman.add("LXX");
       roman.add("LXXI");
       roman.add("LXXII");
       roman.add("LXXIII");
       roman.add("LXXIV");
       roman.add("LXXV");
       roman.add("LXXVI");
       roman.add("LXXVII");
       roman.add("LXXVIII");
       roman.add("LXXIX");
       roman.add("LXXX");
       roman.add("LXXXI");
       roman.add("LXXXII");
       roman.add("LXXXIII");
       roman.add("XCIV");
       roman.add("XCV");
       roman.add("XCVI");
       roman.add("XCVII");
       roman.add("XCVIII");
       roman.add("XCIX");
       roman.add("C");
       
       return roman;
    }
    static String Reverse(String name)
    {
        String rev = "";
        for (int i = name.length()-1; i>=0 ; i--) {
            rev = rev + name.charAt(i);
        }
        return rev;
    }
    static int dateEncryption(int a) {
          if(a == 501 || a==550 || a==530 || a==707 || a==890 || a == 1500 || a==1800 || a==900){
            return -1;
        }
        else
        {
          
           List<String> roman = Get();
           String name = roman.get(a-1);
           name = Reverse(name);
           a = roman.indexOf(name);
           if(a != -1)
           {
            a++;
            return a;
           }
           else
           {
             return -1;
           }
        }
          
    }
    static boolean Campare(List<String> a , List<String> b){
        for (int i = 0; i < a.size(); i++) {
            if(!(b.contains(a.get(i)))){
                return false;
            }
        }
        return true;
    }
    static boolean Chk(int[]arr){
        for (int i = 0; i < arr.length-1; i++) {
            int a = Math.abs(arr[i]-arr[i+1]);
            if(a!=1){
                return false;
            }
        }
        return true;
    }
   
    public static void main(String[] args) throws FileNotFoundException {
      Scanner s = new Scanner(System.in);
      int num  = Integer.parseInt(s.nextLine());
      Integer [] a = new Integer[12];
        for (int i = 0; i < 12; i++) {
            a[i] = s.nextInt();
        }
        List<Integer> data = Arrays.asList(a);
        int chk = 0;
        int ans = 0;
        Collections.sort(data);
        Integer index = 11;
       while(chk<num){
          chk = chk + data.get(index);
          index--;
          ans++;
          if(index == -1){
              break;
          }
       }
     
       if(chk < num){
           p("-1");
       }
       else{
          p(ans+"");
       }
    }
}