Bài 2. Mảnh ghép (LEGO)

Mark là CEO của tập đoàn Space X, sau khi ông tổ chức cho nhân viên của tập đoàn đi du hành vũ trụ về, ông thực hiện dự án mới đó là nghiên cứu một loại mảnh ghép mới để lắp ghép ra các thiết bị không gian có độ dài tùy ý. Loại mảnh ghép này dùng một loại vật liệu mới rất cứng nên không thể cắt hàn như các vật liệu thông thường, nó dùng các ngàm âm dương để liên kết với nhau. Để thuận tiện cho việc lắp ghép các thiết bị, tập đoàn đã sản xuất sẵn \(n\) mảnh ghép, mỗi mảnh ghép có chiều dài nhất định; người ta căn cứ vào chiều dài thiết bị của mình để lấy số lượng các mảnh ghép phù hợp. Chiều dài của thiết bị sau lắp ghép chính là tổng chiều dài của các mảnh ghép được sử dụng.

Một thiết bị có chiều dài \(d\) được gọi là lắp ghép được nếu tồn tại cách chọn các mảnh ghép của từng loại sao cho tổng chiều dài đúng bằng \(d\).

Các thiết bị này sẽ được sử dụng trên các trạm không gian, mỗi trạm có một giới hạn chiều dài \(T\) nhất định. Để đánh giá sự linh hoạt về chiều dài của các mảnh ghép này, người ta tiến hành xem xét có thể lắp ghép được những thiết bị có độ dài bao nhiêu trong khoảng giới hạn của trạm (tức là giới hạn trong đoạn \([0,T]\)).

Hãy giúp Mark thống kê số lượng các chiều dài \(d\) của thiết bị có thể lắp ghép được \((0 \le d \le T)\).

Input

Cho trong file LEGO.INP, có cấu trúc:

• Dòng 1: Chứa hai số nguyên dương \(n\) và \(T\) \((1 \le n \le 2000,\ 0 \le T \le 10^{18})\).
• Dòng 2: Chứa \(n\) số nguyên dương \(a_1,a_2,\ldots,a_n\) là chiều dài của từng mảnh ghép \((1 \le a_i \le 2000)\).

Các số trên cùng một dòng được ghi cách nhau bởi ít nhất một dấu cách.

Output

Ghi ra file LEGO.OUT:

• Dòng 1: Ghi một số nguyên duy nhất là kết quả của bài toán.

Example

2 7
2 5

6

Scoring

• 40% số test tương ứng với 40% số điểm có \(T \le 2\times10^3\).
• 20% số test tương ứng với 20% số điểm có \(T \le 2\times10^4\).
• 20% số test tương ứng với 20% số điểm có \(T \le 2\times10^5\).
• 20% số test còn lại có \(T \le 10^{18}\).