Có món đồ, được đánh số từ đến . Món đồ thứ có trọng lượng là và giá trị là .
Taro quyết định chọn một số món đồ trong món này và bỏ vào một cái túi. Sức chứa của túi là , có nghĩa là tổng trọng lượng của các món đồ được chọn không được vượt quá .
Hãy tìm tổng giá trị lớn nhất có thể của các món đồ mà Taro có thể mang đi. Đây là bài toán cái túi 0/1, nghĩa là mỗi món đồ chỉ có thể được chọn hoặc không được chọn.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên và .
dòng tiếp theo, dòng thứ chứa hai số nguyên và .
Kết quả: In ra một số nguyên duy nhất là 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 món đồ thứ (trọng lượng , giá trị ) và món đồ thứ (trọng lượng , giá trị ). Tổng trọng lượng là , tổng giá trị là .
