Số xu tối thiểu

Trong một dự án thiết kế game, FullHouse Dev được giao nhiệm vụ tối ưu hóa hệ thống tiền tệ trong game. Họ cần phải tìm ra cách để người chơi có thể sử dụng ít xu nhất có thể để đạt được một số tiền nhất định.

Bài toán

FullHouse Dev có một hệ thống tiền tệ gồm \(n\) loại xu, mỗi xu có một giá trị nguyên dương. Nhiệm vụ của họ là tạo ra một số tiền \(x\) bằng cách sử dụng các xu có sẵn sao cho số lượng xu sử dụng là ít nhất.

Ví dụ, nếu các loại xu là {1,5,7} và số tiền cần tạo ra là 11, thì phương án tối ưu là 5+5+1, sử dụng 3 xu.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(x\): số lượng loại xu và số tiền cần tạo ra.
• Dòng thứ hai chứa \(n\) số nguyên \(c_1, c_2, ..., c_n\): giá trị của từng loại xu.

OUTPUT FORMAT:

• In ra một số nguyên: số lượng xu tối thiểu cần sử dụng. Nếu không thể tạo ra số tiền mong muốn, in ra -1.

Ràng buộc:

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

Ví dụ

INPUT

3 11
1 5 7

OUTPUT

3

Giải thích

Với số tiền cần tạo là 11 và ba loại xu có giá trị 1, 5, và 7:

• Phương án tối ưu là sử dụng hai đồng 5 xu và một đồng 1 xu (5+5+1 = 11)
• Tổng cộng cần 3 đồng xu
• Đây là cách sử dụng ít xu nhất để tạo ra số tiền 11