autoput
The government of the land of Baitovia has decided to improve the infrastructure of its routes by building a new highway. The highway is a straight line that is parallel to the Y axis. The length of the route can be very large. The new route will be accessible to more citizens than the current one. It is understood that citizens of a certain city will use the highway if the smallest distance between their city and the highway is not bigger than the number D.
InputIn the first line you are given the number of cities in Baitovia, N <= 50 000 and the number D. They are separated with one space between them. In the following N lines you are given the X and Y coordinates of the i-th city in Baitovia and the number of citizens in that city. Every number in the Input is an integer and it’s less than 100000.
OutputIn the first and only line of the Output file autoput.out you should write the number of citizens of Baitovia that will use the highway. That number will not be larger than 2*10^9.
Input:
Output:
Explanation:
The highway will be the line X=7, so it will be available to the third, fourth and fifth city from the Input.
5 2
11 9 1000
2 5 2000
7 5 10000
5 8 1000
9 2 5000Output:
16000Explanation:
The highway will be the line X=7, so it will be available to the third, fourth and fifth city from the Input.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.