Một kẻ trộm đột nhập vào một cửa hiệu tìm thấy có món hàng có trọng lượng và giá trị khác nhau, nhưng hắn chỉ mang theo một cái túi có sức chứa về trọng lượng tối đa là . Vậy kẻ trộm nên bỏ vào ba lô những món nào để đạt giá trị cao nhất trong khả năng mà hắn có thể mang đi được.
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên dương và ;
dòng tiếp theo, mỗi dòng chứa hai số nguyên dương và mô tả một đồ vật có trọng lượng và giá trị .
