Chuyến công tác (Business trip)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một cây cần tăng ít nhất $k$ xentimét trong năm. Nếu chăm cây ở tháng $i$, cây tăng thêm $a_i$ xentimét; nếu không thì tháng đó không tăng. Có đúng $12$ tháng. Hãy tìm số tháng ít nhất cần chăm, hoặc in $-1$ nếu không thể đạt $k$.

Input

Dòng đầu chứa $k$. Dòng thứ hai chứa đúng $12$ số $a_1,\ldots,a_{12}$.

Output

In số tháng ít nhất cần chọn; in -1 nếu tổng tăng trưởng cả năm vẫn nhỏ hơn $k$.

Subtask

Các giới hạn chung:

• $0 \le k \le 100$.

• $0 \le a_i \le 100$.

• Subtask 1 (20 điểm): $k \le 20$, $a_i \le 20$

• Subtask 2 (30 điểm): $k \le 50$, $a_i \le 50$

• Subtask 3 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

Input

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

Output

2

Giải thích

Chọn hai tháng có mức tăng $3$ và $2$ là đủ đạt $5$; một tháng không thể vì giá trị lớn nhất chỉ là $3$.