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 bài này yếu
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Theo mình thì test mẫu không có bị sai. Mình đi từ 3->5 (mất 2); 5->0 (mất 5). Tổng cộng mất 7 (vừa đủ)
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.