Tìm cách đổi tiền sao cho ít đồng nhất có thể. Có \(n\) đồng mệnh giá lần lượt là \(c_1, c_2... c_n\).

Input

• Dòng thứ nhất có hai số nguyên là \(m\) \(n\). Trong đó \(m\) là số tiền cần đổi, \(n\) là số lượng đồng tiền.
• Dòng thứ hai chứa \(n\) số nguyên \(c_1, c_2... c_n\) là mệnh giá các đồng tiền

Output

• Một số nguyên duy nhất là số lượng đồng ít nhất có thể dùng.

Ràng buộc

• \(1 \le m \le 50000\)
• \(1 \le n \le 20\)
• \(1 \le c_i \le 10000\)
• Tất cả đồng là khác nhau và có chứa đồng 1.

Sample Input 1

55 4
1 5 10 50

Sample Output 1

2