Hide

# Solar Energy You are planning to travel in interstellar space in the hope of finding habitable planets. You have already identified $N$ stars that can recharge your spaceship via its solar panels. The only work left is to decide the orientation of the spaceship that maximizes the distance it can travel.

Space is modeled as a $2$D plane, with the Earth at the origin. The spaceship can be launched from the Earth in a straight line, in any direction. Star $i$ can provide enough energy to travel $T_ i$ distance if the spaceship is launched at an angle of $a_ i$ with the $x$-axis. If the angle is not perfectly aligned, then the spaceship gets less energy. Specifically, if the launch direction makes an angle of $a$ with the $x$-axis, then it gets enough energy to travel distance of

$\max (0, T_ i - s_ i \cdot \mathrm{dist}(a_ i, a))$

from star $i$, where $\mathrm{dist}(a,b)$ is the minimum radians needed to go from angle $a$ to $b$. The distance that the spaceship can travel is simply the sum of the distances that each star contributes. Find the maximum distance $T$ that the starship can travel.

## Input

The first line contains the value $N$, $1\le N\le 10^5$. Following this are $N$ lines each containing three real numbers $T_ i$, $s_ i$, and $a_ i$, with $0<T_ i\le 1\, 000$, $0\le s_ i\le 100$, and $0\le a_ i < 2\pi$. All real numbers in the input have at most $6$ digits after the decimal point.

## Output

On a single line output the maximum distance the spacecraft can travel. Your answer is considered correct if it has an absolute or relative error of at most $10^{-6}$.

Sample Input 1 Sample Output 1
2
100 1 1
100 1 1.5

199.500000

Sample Input 2 Sample Output 2
4
100 1 0.5
200 1 1
100 0.5 1.5
10 2 3

405.500000

CPU Time limit 9 seconds
Memory limit 1024 MB