Trò chơi Mario bao gồm nhân vật hoạt hình Mario và các cây nấm được thiết kế trên một trục số nằm ngang. Có ~N~ cây nấm, cây thứ ~i~ đặt ở vị trí có tọa độ ~X_i~ và chứa ~W_i~ sức mạnh. Mario đang đứng ở vị trí ~X~, có thể di chuyển theo chiều dương hay âm của trục số tùy ý. Nếu đi qua cây nấm ~i~, nó sẽ ăn cây nấm đó và sẽ được tăng thêm ~W_i~ sức mạnh, đồng thời cây nấm ~i~ sẽ biến mất.
Yêu cầu: Thực hiện một lượt chơi để Mario ăn được nhiều sức mạnh nhất, biết rằng mỗi lượt chơi thì Mario chỉ có thể di chuyển quãng đường dài tối đa bằng ~K~.
Input
Từ tệp văn bản MARIO.INP gồm 2 dòng có cấu trúc như sau:
Dòng thứ nhất chứa ba số nguyên ~N~, ~X~ và ~K~ (~1 \leq N \leq 10^5, |X| \leq 10^6, 1 \leq K \leq 10^9~).
Dòng thứ ~i~ trong ~N~ dòng tiếp theo chứa ~2~ số nguyên ~X_i~ và ~W_i~ (~|X_i| \leq 10^6, 1 \leq W_i \leq 10^9~).
Output
Ghi ra tệp văn bản MARIO.OUT một số nguyên duy nhất là tổng sức mạnh tối đa Mario ăn được từ các cây nấm sau một lượt chơi.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~50~ | ~N \leq 10^4~ |
2 | ~50~ | Không có ràng buộc gì thêm |
Sample Input 1
4 3 7
0 9
4 1
5 5
7 8
Sample Output 1
15
Bình luận
test sub lỗi r
ko
bài này hình như test mẫu bị sai phải không ạ