Có ~N~ viên đá quý được đánh số từ 1 đến ~N~. Viên thứ ~i~ (~1 ≤ i ≤ N~) có khối lượng là ~w_i~ và giá trị là ~v_i~.

Nam định chọn một số viên bỏ vào chiếc túi của anh ta để mang về. Sức chứa tối đa của chiếc túi là ~W~, nghĩa là tổng khối lượng các vật có thể mang tối đa là ~W~.

Hãy tìm tổng giá trị lớn nhất của các viên đá mà Nam có thể mang về nhà.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ (~1 ≤ N ≤ 100~) và ~W~ (~1 ≤ W ≤ 10^5~): số lượng viên đá và sức chứa tối đa của chiếc túi.
• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~w_i~ (~1 ≤ w_i ≤ W~) và ~v_i~ (~1 ≤ v_i ≤ 10^9~) — lần lượt là khối lượng và giá trị của viên đá thứ ~i~.

Output

• Xuất ra tổng giá trị lớn nhất của các viên đá mà Nam có thể mang về nhà.

Ví dụ

Input

3 8
3 30
4 50
5 60

Output

90

Giải thích:

Chọn viên đá thứ nhất và thứ 3, chúng có trọng lượng là 3+5=8 vừa với chiếc túi và giá trị là 30+60=90.