Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Business trip

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputWhat 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 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 *a*_{i} (0 ≤ *a*_{i} ≤ 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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/18/2018 17:20:21 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|