Bài toán: Tìm số lượng đồng xu tối thiểu để tạo ra tổng ~ x ~

Đề bài

Xét một hệ thống tiền tệ gồm ~ n ~ đồng xu. Mỗi đồng xu có giá trị nguyên dương. Nhiệm vụ của bạn là tạo ra tổng tiền ~ x ~ bằng cách sử dụng các đồng xu sẵn có sao cho số lượng đồng xu được sử dụng là ít nhất.

Ví dụ: Nếu các đồng xu là ~ \{1, 5, 7\} ~ và tổng cần đạt là ~ 11 ~, thì lời giải tối ưu là ~ 5 + 5 + 1 ~, sử dụng 3 đồng xu.

Input

• Dòng đầu tiên chứa hai số nguyên ~ n ~ và ~ x ~: số lượng đồng xu và tổng cần đạt.
• Dòng thứ hai chứa ~ n ~ số nguyên ~ c_1, c_2, \ldots, c_n ~: giá trị của từng đồng xu.

Output

• In ra một số nguyên: số lượng đồng xu tối thiểu để tạo ra tổng ~ x ~. Nếu không thể tạo được tổng ~ x ~, 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 1:

3 11
1 5 7

Output 1:

3

Giải thích:

• Sử dụng các đồng xu ~ 5 + 5 + 1 = 11 ~, cần 3 đồng xu.

Input 2:

3 15
2 4 6

Output 2:

-1

Giải thích:

• Không thể tạo tổng ~ 15 ~ chỉ với các đồng xu ~ \{2, 4, 6\} ~.