Problem: Sledge Track

Want to try solving this problem? You can submit your code online if you log in or register.

Sledge Track

Time Limit: 1 second
Memory Limit: 40 Mb

For the first time in many years, probably as a consequence of climate change, it has snowed very hard in your area. You decide to take this opportunity to organize a sledge competition in the hills behind your house. You are looking for a nice spot for a track and want to find one that would allow the sledges to reach high speeds, even though there aren't too many steep slopes in the area.

You have found a topographic map of the area, which is drawn using contours. These contours are perfect circles, and the map indicates the altitude of the area touching the inner edge of each circle. The area that is outside all of the circles has an altitude of zero. As these contours are the only information you have about the shape of the hills, you may assume the areas between contours are flat. Two contours never intersect or even touch one another.

Using your map, your goal is to find a track that crosses no more than K circles for some given number K (you don't want the track to be too bumpy), and such that the total difference in altitude between the starting point and the finish point is as large as possible. Your track can have uphill parts, but should never reach an altitude higher than your starting point.

For example, the diagram below shows one such map. If the maximum number of circles you are allowed to cross is K=4, then the track with the largest difference in altitude is shown by the dotted line, which has an altitude difference of 66 - (-2) = 68. The second diagram gives a clearer view of the landscape described by this map (not to scale).

Constraints

For 95% of the available marks:

1 <= C <= 2000, where C is the number of circles on the map;
1 <= K <= 200, where K is the maximum number of circles your track can cross;
-1000 <= X,Y <= 1000, where X and Y form the co-ordinates of the center of a circle;
1 <= R <= 2000, where R is the radius of a circle;
-1000 <= A <= 1000, where A is the altitude of an area.

For 30% of these marks (which form part of the 95% mentioned above):

1 <= C <= 100, where C is the number of circles on the map;

Furthermore, for the remaining 5% of the available marks:

1 <= C <= 40,000, where C is the number of circles on the map.

Input

Your program must read from standard input. The first line of input will contain the integers C K, where C is the number of circles on the map, and K is the maximum number of circles your track can cross.

The following C lines describe the circles, given in increasing order of their radius. Each of these lines describes a circle using four space-separated integers: Xi, Yi, Ri and Ai, where (Xi,Yi) are the coordinates of the center of the circle, Ri is the radius and Ai is the altitude of the area touching the inner edge of the circle.

Output

Your program must write a single line to standard output. This line must contain a single integer, giving the maximum possible difference in altitude you can obtain between the starting point and end point of a track with the constraints described above.

Sample Input

10 4
38 61 2 73
69 34 3 15
61 59 4 30
40 60 5 66
58 44 6 30
71 34 6 -2
47 21 6 45
41 58 8 52
41 57 11 37
48 40 33 10

Sample Output

Scoring

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.