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\)
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 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