Ổ USB (USB Flash Drives)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ ổ USB, ổ thứ $i$ có dung lượng $a_i$ MB. Cần lưu một tệp kích thước $m$ MB và tệp được phép chia giữa nhiều ổ. Hãy tìm số ổ ít nhất cần dùng.

Input

Dòng đầu chứa $n$. Dòng thứ hai chứa $m$. $n$ dòng tiếp theo, mỗi dòng chứa một dung lượng $a_i$.

Output

In số ổ ít nhất cần dùng.

Subtask

Các giới hạn chung:

• $1 \le n \le 100$.

• $1 \le m \le 10^5$.

• $1 \le a_i \le 1000$.

• $\sum a_i \ge m$.

• Subtask 1 (20 điểm): $n \le 10$, $m \le 1000$

• Subtask 2 (30 điểm): $n \le 50$, $m \le 2\cdot10^4$

• Subtask 3 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

Input

3
5
2
1
3

Output

2

Giải thích

Hai ổ dung lượng $3$ và $2$ có tổng đúng $5$ MB, nên dùng $2$ ổ là đủ; không ổ đơn nào đủ $5$ MB.