Có ~n~ đồ vật, đồ vật thứ ~i~ có khối lượng ~w_i~ và giá trị ~v_i~. Bạn được chọn một số đồ vật bất kỳ miễn sao tổng khối lượng của chúng không vượt quá ~S~ cho trước. Hãy tìm cách chọn sao cho tổng giá trị là lớn nhất có thể.

Mỗi đồ vật chỉ được chọn nhiều nhất một lần.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~S~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~w_i~ và ~v_i~.

Kết quả

In ra tổng giá trị lớn nhất có thể thu được.

Ví dụ

Đầu vào:

3 5
1 4
4 1
2 100

Đầu ra:

104

Giải thích: Chọn đồ vật ~1~ và đồ vật ~3~: tổng khối lượng ~1 + 2 = 3 \le 5~, tổng giá trị ~4 + 100 = 104~. Không thể thêm đồ vật ~2~ vì khi đó khối lượng thành ~7 > 5~.

Giới hạn

• ~1 \le n \le 20~
• ~1 \le S \le 10^9~
• ~1 \le w_i, v_i \le 10^9~

Lưu ý rằng ~S~ rất lớn nên không thể quy hoạch động theo khối lượng; tuy nhiên ~n \le 20~ nên số cách chọn chỉ nhiều nhất là ~2^{20}~. Kết quả có thể lên tới ~2 \cdot 10^{10}~, không vừa trong số nguyên 32 bit.