PEG Judge - WC18 #3 - Holey Travels

Woburn Challenge 2018-19 Round 3 - Senior Division

Problem 4: Holey Travels

When it comes down to it, there's nothing that the members of Team Rocket enjoy more than the simple, familiar things in life. In other words, digging holes to trap Pokémon trainers and steal their Pokémon.

Today, N (1 ≤ N ≤ 1000) Pokémon trainers will be traveling over an open field which can be represented as an infinite 2D plane. The i-th Pokémon trainer will be walking along the infinite, straight line which passes through two distinct points (X1_i, Y1_i) and (X2_i, Y2_i) (−10,000 ≤ X1_i, Y1_i, X2_i, Y2_i ≤ 10,000, (X1_i, Y1_i) ≠ (X2_i, Y2_i)). Multiple trainers may walk along exactly the same path. Note that each path extends infinitely in both directions (it's neither a line segment nor a ray). Team Rocket don't care in which direction along this path the trainer will be walking. What they do care about is the fact that the i-th trainer will have P_i (1 ≤ P_i ≤ 1,000,000) Pokémon with them!

Jessie, James, and Meowth have time to dig a single hole somewhere on this infinite field before the trainers begin walking along their paths. This hole will be a circle with real-valued radius R (1 ≤ R ≤ 100,000), centered at any point (with real-valued coordinates) of their choice.

Once the hole has been dug, each trainer whose path turns out to intersect with or touch the hole's circle (inclusively) will fall into it, with all of their Pokémon becoming trapped in the hands of Team Rocket. What's the maximum number of Pokémon which Team Rocket can trap by choosing an optimal excavation location?

Subtasks

In test cases worth 8/40 of the points, N ≤ 2.
In test cases worth another 20/40 of the points, N ≤ 100.

Input Format

The first line of input consists of a single integer, N, and 1 real number, R.
N lines follow, the i-th of which consists of five space-separated integers, X1_i, Y1_i, X2_i, Y2_i, and P_i, for i = 1..N.

Output Format

Output a single integer, the maximum number of Pokémon which Team Rocket can trap. It's guaranteed that increasing or decreasing R by up to 10⁻⁵ would not change the answer.

Sample Input 1

4 3.0
3 0 5 4 3
-2 5 7 0 8
-5 -5 7 1 9
1 6 -7 1 12

Sample Output 1

Sample Input 2

5 2.1
2 1 6 1 2
3 -2 -5 -2 3
7 5 1 5 2
-5 -3 -4 -3 1
-6 -7 4 -7 4

Sample Output 2

Sample Explanation

The following diagram illustrates the first case, with the Pokémon trainers' paths indicated in blue, and one possible optimal hole location (trapping 3 + 8 + 12 = 23 Pokémon) indicated in brown: