406821: GYM102565 J Statue

Jimmy is the governor of a very important city in AGM land. He recently listened to a beautiful song called "Vreau sa-mi fac statuie in fata portii" (which translates to "I want to make a statue of myself in front of the gate") and now Jimmy wants to make a statue of himself somewhere in the city so people can admire his face even more.

In Jimmy's city there are $$$N$$$ ($$$1 \leq N \leq 10^5$$$) houses positioned in a 2D plane. House number $$$i$$$ has coordinates $$$(x_i, y_i)$$$, where $$$0 \leq x_i \leq 100$$$ and $$$0 \leq y_i \leq 10^9$$$ . In addition, there are $$$M$$$ ($$$1 \leq M \leq 10^5$$$) roads, each joining a pair of houses. The governor knows how many people travel everyday on each road. Because he wants to make as many of his people happy as possible, he wants to place the statue somewhere so that the statue can be seen by the maximum number of people.

Sadly, the city's budget forced Jimmy to make a statue that can only be seen from a distance not bigger than $$$R$$$ ($$$1 \leq R \leq 10^4$$$). Being precautious, when counting the number of people that see the statue, Jimmy will add the number of travellers of a road only if the statue can be seen from both of the houses connected by it.

Your task is to make Jimmy and his people happy by finding the perfect spot for his statue. It should be placed in a point with integer coordinates so that the number of people that see it is maximised. Print this number.

The first line of the input will contain $$$3$$$ integers: $$$N$$$, $$$M$$$, $$$R$$$ as defined above.

The following $$$N$$$ line will contain $$$2$$$ integers each: $$$x_i$$$ and $$$y_i$$$, the coordinates of house $$$i$$$.

The last $$$M$$$ lines each contain $$$3$$$ integers $$$a$$$ ($$$1 \leq a \leq N$$$), $$$b$$$ ($$$1 \leq b \leq N$$$), $$$p$$$ ($$$1 \leq p \leq 10^9$$$) meaning there is a 2 way road between house $$$a$$$ and $$$b$$$ with $$$p$$$ people travelling on it.

There can be multiple edges between the same houses.

Houses cannot have roads to themselves.

The output should contain the maximum number of people that can see the statue.

3 3 3
4 4
7 3
4 8
1 3 3
1 2 6
2 3 8

6

If the statue is placed at $$$(6, 4)$$$ then 6 people will be able to admire Jimmy.