Tên trộm
Đề bài
Mô tả
Một tên trộm đột nhập vào một ngôi nhà có món đồ. Món đồ thứ có khối lượng và giá trị . Tên trộm có một chiếc túi chịu được khối lượng tối đa . Nếu tổng khối lượng các món đồ trong túi vượt quá , túi sẽ rách và tên trộm không mang được gì.
Sau khi xếp đồ vào túi, tên trộm nghĩ: "Mình xách túi bằng một tay, vậy tay còn lại có thể cầm thêm một món đồ nữa." Theo ý nghĩ đó, tên trộm dùng tay còn trống để cầm thêm một món đồ, với điều kiện khối lượng của nó không vượt quá .
Hãy xác định tổng giá trị lớn nhất của các món đồ mà tên trộm có thể mang đi.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên dương , và (, ).
- Mỗi dòng trong dòng tiếp theo chứa hai số nguyên dương và (, ).
Dữ liệu ra
In ra một dòng chứa tổng giá trị lớn nhất mà tên trộm có thể mang đi.
Ràng buộc
- ,
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 10 2 2 5 1 9 4 6 |
20 | Túi chứa được cả ba món đồ, tổng giá trị là . |
| 3 2 4 2 5 1 9 4 6 |
15 | Tên trộm cho món đồ thứ vào túi và cầm món đồ thứ trên tay. |
Bình luận