Business trip

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

A plant must grow by at least $k$ centimeters during the year. If it is watered in month $i$, it grows by $a_i$ centimeters; otherwise it does not grow in that month. There are exactly 12 months. Find the minimum number of months needed, or print $-1$ if impossible.

Input

The first line contains $k$. The second line contains exactly 12 integers $a_1,\ldots,a_{12}$.

Output

Print the minimum number of selected months, or -1 if the target cannot be reached.

Subtasks

General constraints:

• $0 \le k \le 100$.

• $0 \le a_i \le 100$.

• Subtask 1 (20 points): $k \le 20$, $a_i \le 20$

• Subtask 2 (30 points): $k \le 50$, $a_i \le 50$

• Subtask 3 (50 points): No additional constraints.

Examples

Input

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

Output

2

Explanation

Choose two months with growth values $3$ and $2$. Their sum reaches $5$, while no single month reaches the target.