CSES - Minimizing Coins | Giảm thiểu đồng xu

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Thời gian:
Pypy 3 1.5s
Tác giả:
Flower_On_Stone , kitsune
Dạng bài
Điểm: 1200 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Hãy xét một hệ thống tiền bao gồm \(n\) đồng xu. Mỗi đồng xu có giá trị là một số nguyên dương. Nhiệm vụ của bạn là tạo ra một khoản tiền \(x\) bằng cách sử dụng các đồng xu có sẵn sao cho số lượng đồng xu là tối thiểu.

Ví dụ: nếu các đồng xu là \(\{1,5,7\}\) và tổng mong muốn là \(11\), một giải pháp tối ưu là \(5 + 5 + 1\), cần \(3\) đồng xu.

Input

  • Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(x\): số lượng đồng xu và tổng số tiền mong muốn.
  • Dòng thứ hai có \(n\) số nguyên phân biệt \(c_1, c_2, \ldots, c_n\): giá trị của mỗi đồng xu.

Output

  • In một số nguyên: số lượng đồng xu tối thiểu. Nếu không thể tạo ra tổng mong muốn, hãy in \(−1\).

Constraints

  • \(1 \leq n \leq 100\)
  • \(1 \leq x \leq 10 ^ 6\)
  • \(1 \leq c_i \leq 10 ^ 6\)

Example

Sample input

3 11
1 5 7

Sample output

3

Bình luận