Đổi pin ít lần nhất

Bối cảnh và bài toán

Một trạm bảo trì có n loại pin, loại i bổ sung đúng c_i đơn vị năng lượng. Mỗi lần thay chỉ dùng một pin và có thể dùng một loại nhiều lần.

Yêu cầu

Đạt đúng mức năng lượng x với số pin ít nhất; nếu không thể, in -1.

Input

Dòng 1: n x. Dòng 2: n giá trị c_i.

Output

In số pin ít nhất hoặc -1.

Ràng buộc

• 1 <= n <= 100
• 1 <= x <= 10^5
• 1 <= c_i <= 10^5

Chấm điểm

Ví dụ 1

Input

3 11
1 5 7

Output

3

Giải thích. Ví dụ nhỏ giúp kiểm tra cách mô hình hóa trạng thái và kết quả cuối; khi tự giải, cần suy luận từ ràng buộc thay vì suy đoán từ sample.

Ví dụ 2

Input

2 3
2 4

Output

-1

Giải thích. Hãy đối chiếu với edge case: trạng thái đầu, trạng thái không đạt được, tie hoặc biên chỉ số tùy bài.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Minimizing Coins. Bản FULLHOUSE DEV đã biên tập bối cảnh/format và ràng buộc khi cần để khớp scope-lock của khóa học.