Có vật, vật thứ có trọng lượng và giá trị .
Taro quyết định chọn một số trong vật này và bỏ chúng vào một chiếc túi. Sức chứa của túi là , nghĩa là tổng trọng lượng của các vật được chọn phải không vượt quá .
Yêu cầu: Tìm tổng giá trị lớn nhất có thể của các vật mà Taro chọn.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên và .
dòng tiếp theo, mỗi dòng chứa hai số nguyên và .
Kết quả:
In ra tổng giá trị lớn nhất có thể.
Ví dụ:
Dữ liệu:
3 8
3 30
4 50
5 60
Kết quả:
90
Giải thích: Chọn vật 1 và 3. Tổng trọng lượng là . Tổng giá trị là .
