An có rất nhiều tiền trong ngân hàng Thụy Sĩ, một hôm An cần rút một số tiền \(N\) \((N \le 10^5)\), ngân hàng chỉ có \(K\) \((K \le 10^3)\) loại mệnh giá lần lượt là \(A_1, A-2,...A_k\). Vì lý do đặc biệt nên An mong muốn số tờ tiền rút được là ít nhất.

Dữ liệu vào:

• Dòng thứ nhất chứa \(2\) số nguyên dương \(N\) và \(K\). Trong đó, \(N\) là số tiền cần rút, \(K\) là loại tiền mệnh giá
• Dòng thứ hai chứa \(K\) số nguyên dương \(A_1, A_2... A_k\) lần lượt là mệnh giá của các tờ tiền.

Kết quả

Chứa \(1\) số nguyên dương duy nhất là số tờ tiền ít nhất mà An rút được, nếu không thể in ra \(-1\)

Input 1

125 6
1 2 5 10 20 50

Output 1

4

Input 2

5 3
2 4 6

Output 2

-1

Ràng buộc

• 20% test với \(K=2\) và \(A_i\) khác nhau từng đôi một.
• 30% test với \(K \le 10, N \le 100\) và \(A_i\) khác nhau từng đôi một.
• 50% test còn lại không giới hạn gì khác.