Một nhà thám hiểm chuẩn bị cho một chuyến đi dài ngày vào rừng. Anh ta mang theo một chiếc túi có thể chứa tối đa s kg. Để sống sót trong rừng, anh ta cần mang theo một số vật phẩm thiết yếu. Mỗi vật phẩm có khối lượng và giá trị nhất định.

Cụ thể, có n vật phẩm, vật phẩm thứ i có:

• Khối lượng: w_i​ kg
• Giá trị sử dụng: v_i đồng

Nhà thám hiểm muốn chọn một tập hợp các vật phẩm sao cho tổng khối lượng không vượt quá s kg, đồng thời tổng giá trị sử dụng của các vật phẩm được chọn là lớn nhất.

Yêu cầu: Hãy viết một chương trình để giúp nhà thám hiểm lựa chọn các vật phẩm một cách tối ưu.

Dữ liệu vào: Cho từ tệp THAMHIEM.INP có dạng:

• Dòng đầu tiên chứa hai số nguyên n và s  ( 1 ≤ n ≤ 10⁵, 1 ≤ s ≤ 10⁵)
• n dòng tiếp theo, mỗi dòng chứa hai số nguyên w_i ​ và v_i ​ ( 1 ≤ w_i ≤ S1, 1 ≤ v_i ≤ 10⁵)

Dữ liệu ra: Ghi ra tệp THAMHIEM.OUT có dạng:

• Một số nguyên duy nhất là tổng giá trị sử dụng lớn nhất mà nhà thám hiểm có thể đạt được.

Ví dụ: