MARIO


Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 512M

Problem type

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

There are no comments at the moment.