Có ~n~ đồ vật.

Vật thứ ~i~ có khối lượng ~w_i~ và giá trị ~v_i~.

Bạn có chiếc ba lô sức chứa tối đa ~W~. Mỗi đồ vật chọn hoặc không chọn (0/1).

Hãy tính tổng giá trị lớn nhất có thể mang theo mà tổng khối lượng không vượt quá ~W~.

Input

• Dòng 1: ~n, W~ trong đó ~1 \le n \le 2000,1 \le W \le 2\cdot 10^5~
• ~n~ dòng tiếp theo: mỗi dòng gồm ~w_i, v_i~ trong đó ~1 \le w_i \le W,0 \le v_i \le 10^9~

Output

• Một số nguyên: giá trị lớn nhất.

Ví dụ

Input

3 7
3 4
4 5
2 3

Output

9