405357: GYM101915 B Ali and Wi-Fi

Ali lives in a very crowded city and a very large apartment. His apartment looks like an almost infinite 2D plane. In this city almost all his neighbors have WiFi networks, except for him. Precisely, from his apartment his laptop can receive N WiFi networks.

One day Ali wrote a program that can hack his neighbors' WiFi networks. Furthermore, he learned how to stand in a point, hack almost all the WiFi networks that reaches that point, and join them in one ultra-speed network.

Each WiFi network is described as a circle with its center on the point (x, y), a radius equal to R and a network speed equal to S.

However, Ali's program can join at most M networks. When Ali's program joins many networks, the resulting network will have the total sum for speeds of all networks.

Ali wants to choose a point at his apartment that will get him the maximum total speed of WiFi networks. Can you help him calculate the maximum total WiFi network speed he can get if he chooses his location optimally?

The first line contains an integer T, the number of test cases.

The first line of each test contains (1 ≤ N ≤ 100) the number of WiFi networks and (1 ≤ M ≤ 100) the maximum number of networks Ali can join.

The following N line contains the description of N WiFi networks. The center coordinates (0 ≤ x, y ≤ 10³) , the radius (1 ≤ R ≤ 10³) and the network speed (0 ≤ S ≤ 10⁶) .

For each test case print a single line, containing a single integer, denoting the maximum total WiFi network speed Ali can get, if he chooses his location optimally.

1
3 2
0 0 2 5
4 0 1 10
2 2 4 2

12