Bessie tội nghiệp làm ở cửa hàng tiện lợi ngay bên kia biên giới Slobbovia. Tiền xu khác USA, giá trị đổi hàng ngày!

Giúp trả tối ưu cho khách Slobbovia: $C$ xu ($1 \le C \le 1000$) bằng $N$ mệnh giá ($1 \le N \le 10$). Mọi kiểm thử giải được bằng xu cho sẵn.

Có 50, 25, 10, 5, 1, tối ưu ít xu nhất cho 93 xu là $1 \times 50$, $1 \times 25$, $1 \times 10$, $1 \times 5$, $3 \times 1$: tổng 7 xu.

Khó đến đâu? Hai kiểm thử cuối sẽ thách thức.

Dữ liệu vào

Đọc đầu vào chuẩn.

Dòng 1: số nguyên $C$ và $N$ cách nhau bởi dấu cách.

Các dòng $2..N+1$: số nguyên phân biệt mỗi dòng, mệnh giá dùng được.

Dữ liệu ra

Ghi đầu ra chuẩn.

Dòng 1: số nguyên là ít xu nhất tạo $C$ xu.

Ví dụ

Dữ liệu vào 1

93 5
25
50
10
1
5

Dữ liệu ra 1

7

Nguồn: USACO tháng 1 năm 2007, đồng