Túi ba gang và kho báu bí mật

Trong một chuyến phiêu lưu đầy thử thách, bạn theo chân chú chim thần kỳ đến một hang động chứa kho báu. Hang động này được canh giữ bởi một loài chim khổng lồ - Hắc Điểu. Tuy nhiên, chú chim thần kỳ giúp bạn vượt qua Hắc Điểu và tiến vào nơi cất giữ những khối vàng quý giá.

Hang động chứa \(n\) khối vàng, mỗi khối có khối lượng là \(m_i\). Tuy nhiên, bạn chỉ có một chiếc túi ba gang với sức chứa tối đa là \(M\). Nhiệm vụ của bạn là tìm xem có bao nhiêu cách khác nhau để chọn một số khối vàng sao cho tổng khối lượng không vượt quá \(M\).

Hãy nhớ rằng, hai cách được coi là khác nhau nếu tồn tại ít nhất một khối vàng mà cách này chọn nhưng cách kia thì không, bất kể thứ tự lựa chọn

Input

Dữ liệu được nhập từ tiêu chuẩn đầu vào với cấu trúc sau:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(M\) \((1 \leq n \leq 40, 1 \leq M \leq 10^6)\).
• Dòng thứ hai chứa \(n\) số nguyên \(m_1, m_2, \ldots, m_n\) \((1 \leq m_i \leq M)\), biểu thị khối lượng của từng khối vàng.

Output

In ra một số duy nhất là tổng số cách có thể chọn các khối vàng sao cho tổng khối lượng không vượt quá \(M\).

Example

4 10
3 10 5 4

8