Chọn hành trình
An đang du lịch tại Hà Nội. Sau khi lướt mạng, cậu đã liệt kê ra $N$ địa điểm cậu muốn đến. Trong đó, địa điểm thứ $i$ có giá vào cổng là $a_i$. Tuy nhiên, do trước đó đã dùng quá nhiều tiền, hiện tại cậu chỉ còn $K$ đồng.
Hãy giúp An biết cậu có bao nhiêu cách chọn địa điểm sao cho tổng số tiền không vượt quá $K$ đồng.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $N,K \ (0<N\le 36; 0<K<10^{10})$;
- Dòng tiếp theo chứa $N$ số nguyên $a_i \ (0<a_i<10^9)$.
Kết quả
- Kết quả bài toán.
Ví dụ
Ví dụ 1
input
5 10
3 4 2 5 6
output
17
Comments