Chọn hành trình


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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

There are no comments at the moment.