Một nhà thám hiểm đang chuẩn bị cho chuyến đi khám phá kho báu trong một khu rừng bí ẩn. Anh ta có một chiếc ba lô với sức chứa tối đa là 𝑊 𝑛vật phẩm trước mặt. Mỗi vật phẩm thứ 𝑖có trọng lượng ~w_i~ và giá trị ~v_i~. Nhiệm vụ của bạn là giúp nhà thám hiểm chọn ra một số vật phẩm sao cho tổng trọng lượng không vượt quá ~W~ nhưng tổng giá trị nhận được là lớn nhất.

Dữ liệu

• Dòng đầu gồm số nguyên ~n~ và ~W~ ~(1 ≤ n ≤ 100, 1 ≤ w ≤ 10^9)~
• ~n~ dòng tiếp theo, dòng thứ ~i~ là trọng số ~w_i~ và giá trị ~v_i~ của đồ vật thứ ~i~ ~(1 ≤ w_i ≤ W, 1 ≤ v_i ≤ 10^3)~

Kết quả

• Gồm 1 số duy nhất là đáp án cần tìm

Ví dụ

Dữ liệu

3 8
3 30
4 50
5 60

Kết quả

90

Ràng buộc