Santa's Route

Submit solution

Points: 10
Time limit: 2.0s
PyPy 2 4.0s
PyPy 3 4.0s
Memory limit: 256M

Problem type

It is December the 23rd, and all the final preparations are being made for Christmas Day.

You are an elf in the logistics division of the North Pole. You have been tasked with planning Santa's route to maximize the number of people that received a present.

There are \(N\) cities, where the \(i\)-th city is located at \((x_i, y_i)\) and has a population of \(p_i\).

Santa's reindeers can travel at most \(D\) units before needing to rest, because of this Santa can only travel between two cities if the Euclidean distance between them is less than or equal to \(D\).

If Santa visits a city, every person that lives there will receive one present.

If Santa can start from any city, what is the maximum number of people that will receive a present?


\(1 \le N \le 2000\)

\(1 \le D \le 10^9\)

\(1 \le x_i, y_i, p_i \le 10^9\)

Input Specification

The first line contains two integers \(N\) and \(D\), the number of cities Santa must visit, and maximum distance Santa can travel without stopping.

The next \(N\) lines contains the locations of the cities. The \(i+1\)-th line contains three integers, \(x_i\), \(y_i\), \(p_i\), which is the location of the \(i\)-th city.

Output Specification

Output the maximum number of presents that can be given, if Santa can start from any city.

Sample Input 1

3 1
1 1 2
2 1 1
2 3 4

Sample Output 1


Sample Input 2

6 3
6 10 4
10 2 5
1 8 3
9 4 2
8 9 5
8 7 2

Sample Output 2



There are no comments at the moment.