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.
def find_min_num_months_to_water_flower(min_flower_growth,
                                        growth_potential_by_month):
    """
    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 a i 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 in which to water the
    flower, given that the flower should grow no less than k centimeters.

    Input:
    min_flower_growth: <int>
    Contains an integer k (0 ≤ k ≤ 100) which represents the minimum number of
    centimeters the flower must grow by.

    growth_potential_by_month: <str>
    Contains twelve space-separated integers where the i-th (1 ≤ i ≤ 12)
    number in the line represents a_i (0 ≤ a_i ≤ 100), the number of
    centimeters the flower will grow in the ith month if watered.

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

    # Split elements in the growth_potential_by_month string by spaces and
    # return a list of strings where each element represents the growth
    # potential for the flower in a particular month of the year
    growth_potential_by_month_list = growth_potential_by_month.split(" ")
    # Convert list<str> to list<int> using built-in map() function
    growth_potential_by_month_list = list(map(int,
                                              growth_potential_by_month_list))

    # Check if the growth potential of the flower as set in the growth
    # potential variable can exceed the minimum growth limit
    if sum(growth_potential_by_month_list) < min_flower_growth:
        print(-1)
        return 0

    # If the growth potential of the flower can exceed the minimum growth
    # limit, then find and remove maximums from the growth potential list
    # until the minimum growth limit is exceeded. Number of months needed is
    # answer
    else:
        flower_growth = 0
        min_num_months = 0
        while flower_growth < min_flower_growth:
            max_growth = max(growth_potential_by_month_list)
            flower_growth += max_growth
            growth_potential_by_month_list.remove(max_growth)
            min_num_months += 1

    print(min_num_months)

min_growth_needed = int(input())
growth_potential_by_month_user = input()
find_min_num_months_to_water_flower(min_growth_needed,
                                    growth_potential_by_month_user)

# Examples
# inputCopy
# 5
# 1 1 1 1 2 2 3 2 2 1 1 1
# outputCopy
# 2
# inputCopy
# 0
# 0 0 0 0 0 0 0 1 1 2 3 0
# outputCopy
# 0
# inputCopy
# 11
# 1 1 4 1 1 5 1 1 4 1 1 1
# outputCopy
# 3