408282: GYM103076 E Death Star

The death star is the dreadful symbol of the Galactic Empire war machine. It's a space station with spherical format, big as a moon and armed with a superlaser capable of destroying planets.

Originally, its laser mechanism operated with a single shot, demanding a lot of time and energy to be reloaded. But recent research introduced a new technology of continuous radiation emission, enabling the destruction of multiple planets in sequence.

Grand Moff Tarkin is conducting the test phase of this new system. He would like to take this opportunity to eliminate some of the Rebel's Alliance bases that could be located in nearby planets. But this attack must be planned with caution, as several planets are occupied by imperial troops that would be exterminated.

The planets nearby are represented as coordinates on a cartesian plane, with the death star located on the origin. The superlaser is modeled as a semi-straight line starting on the origin, that sweeps the plane in an uninterrupted rotation movement. The region covered must always be continuous (as a pizza slice). Notice that the region could englobe no planet.

Determine the largest advantage in the number of troops that the Galactic Empire could acquire with this attack.

The first line of the input contains a single integer $$$N$$$, $$$(1 \leq N \leq 10^5)$$$, the number of planets.

It follows $$$N$$$ lines, with information about the problem. Each of them has four integers $$$x_i$$$, $$$y_i$$$, $$$a_i$$$ and $$$s_i$$$ $$$(-10^9 \leq x_i, y_i \leq 10^9, 0 \leq a_i, s_i \leq 10^9)$$$ — the cartesian coordinates of the i-th planet and the garrisons's sizes of the Rebel's Alliance and the Galactic Empires located on the planet.

It's guaranteed that no planet is positioned on the origin and no pair of them have the same coordinates.

Output a single integer – the maximum possible difference between the number of losses of the Rebel's Alliance and the Galactic Empire after the attack of the new superlaser.

8
-5 4 10 4
7 -8 3 2
-12 -3 4 7
5 4 12 7
-7 13 1 2
2 9 5 8
10 -4 6 10
-7 -7 5 4

7