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 \leq 10^5)\), ngân hàng chỉ có \(K\) \((K \leq 10^3)\) loại mệnh giá lần lượt là \(A_1, A_2, \ldots, 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.

Input

• 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à số loại tiền mệnh giá.
• Dòng thứ hai chứa \(K\) số nguyên dương \(A_1, A_2, \ldots, A_K\) lần lượt là mệnh giá của các tờ tiền.

Output

• Ghi ra một 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\).

Example

125 6
1 2 5 10 20 50

4

5 3
2 4 6

-1

Scoring

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