Rút tiền (THTB ĐN 2023)

Điểm: 1200 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: TIEN.inp

Output: TIEN.out

Tác giả:

Sunlight

Dạng bài

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,\dots,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, Output và Subtasks

Input: (TIEN.inp)

Dòng đầu tiên 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,\dots,a_k$ lần lượt là mệnh giá của các tờ tiền

Output: (TIEN.out)

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

Subtasks

Subtask 1 $(20\%)$ : $k=2$ và $a_i$ khác nhau đôi một
Subtask 2 $(30\%)$ : $k\le 10, n\le 100$ và $a_i$ khác nhau đôi một
Subtask 3 $(50\%)$ : Không có ràng buộc gì thêm

Sample 1

Input (TIEN.inp)

125 6
1 2 5 10 20 50

Output (TIEN.out)

Note

Số tờ tiền ít nhất có thể lấy là 4 tờ gồm 2 tờ mệnh giá $50$ , 1 tờ mệnh giá $20$ , 1 tờ mệnh giá $5$

Sample 2

Input (TIEN.inp)

5 3
2 4 6

Output (TIEN.out)

-1

Note

Không có cách nào để các tờ tiền mệnh giá $2, 4, 6$ tạo thành số tiền là $5$ cho nên in ra -1

Bình luận

Không có bình luận nào.