Cho n mệnh giá tiền a₁, a₂, …, aₙ và giới hạn giao dịch T. Mỗi mệnh giá được dùng không hạn chế số lần.

Đếm số số nguyên x (0 ≤ x ≤ T) có thể thanh toán chính xác bằng tổng các đồng tiền thuộc những mệnh giá đã cho. Giá trị 0 luôn thanh toán được bằng cách không dùng đồng tiền nào.

Dữ liệu vào

Dòng đầu chứa n, T (1 ≤ n ≤ 2000, 0 ≤ T ≤ 10¹⁸).

Dòng thứ hai chứa n số nguyên a₁, …, aₙ (1 ≤ aᵢ ≤ 2000).

Kết quả

Một số nguyên là số giá trị thanh toán được.

Ví dụ

Input

5 10000
100 200 500 1000 2000

Output

101

Đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn. Mỗi test được chấm độc lập.