Thầy Phùng Quang Ngọc đang chọn đội hình Pickleball chuẩn bị cho một giải đấu quan trọng. Thầy có Pickleballer (đánh số từ 1 đến ) và cần chọn ra một đội hình gồm Pickleballer để tham gia thi đấu. Mỗi Pickleballer có một chỉ số sức mạnh và một chỉ số tinh thần . Thầy muốn chọn ra một đội hình có tổng sức mạnh lớn nhất, đồng thời đảm bảo rằng chênh lệch giữa chỉ số tinh thần cao nhất và thấp nhất trong đội không vượt quá một ngưỡng cho trước.
Yêu cầu: Hãy giúp thầy Ngọc tìm ra tổng sức mạnh lớn nhất có thể của đội hình thỏa mãn điều kiện trên.
Dữ liệu:
Dòng đầu tiên chứa ba số nguyên ();
dòng tiếp theo, mỗi dòng chứa hai số nguyên () là chỉ số sức mạnh và tinh thần của Pickleballer thứ .
Kết quả:
Một số nguyên duy nhất là tổng sức mạnh lớn nhất có thể. Nếu không có đội hình nào thỏa mãn, in ra .
Ví dụ:Dữ liệu:
5 3 2
5 3
7 5
2 8
9 4
3 6
Kết quả:
21
Giải thích: Chọn các Pickleballer 1, 2, 4 có tổng sức mạnh là và chênh lệch tinh thần là .
Giới hạn:
Subtask #1 (20% số điểm): .
Subtask #2 (20% số điểm): .
Subtask #3 (20% số điểm): .
Subtask #4 (20% số điểm): .
Subtask #5 (20% số điểm): Không có ràng buộc bổ sung.
