Tại vương quốc HT cón đồng xu mệnh giá a[1], a[2],... , a[n]. Trong đó có đồng xu mệnh giá 1 đồng. HD và HP đều có số lượng vô hạn các đồng xu với đủ các mệnh giá, HD cần đưa cho em HP một khoản tiền là s đồng để mua kem, HD đưa cho em HP một số đồng xu và HP phải trả lại cho Anh một số đồng xu nếu số tiền Anh HD đưa lớn hơn S.

Yêu cầu:Hãy tính tổng số đồng xu tối thiểu mà HD và HP phải trao đổi để em HP nhận được đúng S đồng.

Input

• Dòng thứ nhất: Hai số nguyên dương S, n (1 < s < 10000, 2 < n <= 100)
• Dòng thứ hai: Dãy N số nguyên a[1], a[2], ..., a[n]cách nhau một khoảng trắng (1 <= i <= n, a[i] <= 3000)

Output

• Một số nguyên duy nhất là kết quả bài toán

Sample

Input #1

50  6 
1 2 3 7 27 33

Output #1

4

Hint

50 = 27 + 27 − 1 − 3

Problem source: ziwok