TV tower#829
A television company has a map of the country showing the locations of cities and their respective populations. They want to install a TV tower in a way that maximizes the number of residents who can receive TV broadcasts. The signal from the TV tower can be received at all points within a distance of or less from it. The tower can be installed only at one of the cities (for safety reasons).
The input starts with the radius 0 \leq R \leq 10000 and the number of cities (1 \leq N \leq 100). Then, for each city, its coordinates and its population are given. All coordinates are integers with absolute value not exceeding . The population for each city is a non-negative integer not exceeding .
Output two numbers separated by a space: first, the maximum number of residents who can receive the signal from the TV tower, and second, the index of the city where the TV tower should be installed.
Example 1