MARIO
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 nằm ngang. Có \(N\) cây nấm, cây nấm thứ \(i\) đặt tại vị trí \(x_i\) và chứa \(w_i\) sức mạnh.
Mario đang ở vị trí \(P\), có thể đi theo chiều dương hay âm của trục tùy ý. Nếu đi qua cây nấm thứ \(i\), nó sẽ ăn cây nấm đó và sức mạnh của nó sẽ tăng lên \(w_i\), đồ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 là \(K\).
Input
Dòng 1 chứa 3 số nguyên \(N,P,K (1≤N≤10^5,|P|≤10^6,1≤K≤10^9 ).\)
Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa hai số nguyên \(x_i,w_i (|x_i |≤10^6,1≤w_i≤10^9).\)
Output
- Ghi một số nguyên dương là tổng sức mạnh tối đa Mario ăn được sau một lượt chơi.
Sample Input
4 3 7
0 9
4 1
5 5
7 8
Sample Output
15
Comments