Problem
Con gái của Vua xứ Flatland sắp kết hôn với Hoàng tử Charming.
Hoàng tử muốn tặng công chúa báu vật nhưng lại không biết nên chọn viên kim cương nào trong bộ sưu tập của mình.
Có n viên kim cương trong bộ sưu tập của hoàng tử, mỗi viên được đặc trưng bởi trọng lượng v
i và giá trị v
i.
Hoàng tử muốn tặng những viên kim cương đắt tiền nhất, nhưng nhà vua thông minh và sẽ không nhận những viên kim cương có tổng trọng lượng lớn hơn R. Mặt khác, hoàng tử sẽ cho rằng mình tham lam đến hết đời nếu tặng kim cương có tổng trọng lượng nhỏ hơn L.
Hãy giúp hoàng tử chọn một bộ kim cương có tổng giá trị cao nhất sao cho tổng trọng lượng nằm trong phân khúc [L, R].
Đầu vào:
Dòng đầu tiên chứa số n (1 <= n <= 32), L và R (0 <= L <= R <= 10
18).
N dòng tiếp theo mô tả các viên kim cương và mỗi dòng chứa hai số - trọng lượng và giá trị của viên kim cương tương ứng (1 <= wi, vi <= 10
15).
Đầu ra:
Dòng đầu tiên của kết quả phải chứa k - số lượng kim cương để tặng cho công chúa.
Dòng thứ hai phải chứa số lượng viên kim cương được tặng.
Kim cương được đánh số từ 1 đến n theo thứ tự chúng xuất hiện trong đầu vào.
Nếu không thể soạn quà cho công chúa, hãy in 0 ở dòng đầu tiên của kết quả.
Ví dụ:
| Đầu vào |
Đầu ra |
3 6 8
3 10
7 3
8 2 |
1
2 |