In a workshop there are $$$n$$$ cables laid out on a plane. Cable $$$i$$$ is the straight segment joining $$$A_i=(x_{i,1},y_{i,1})$$$ with $$$B_i=(x_{i,2},y_{i,2})$$$ and has a value $$$w_i$$$.
At the origin $$$O=(0,0)$$$ there is a machine with two lasers. Each laser occupies an infinite line passing through the origin. The two lines are perpendicular and can rotate together, always keeping an angle of $$$90^\circ$$$ between them.
You must choose an orientation of the machine and activate it only once. Both lasers are activated simultaneously and go through all the cables they meet, without stopping.
An orientation is valid if it satisfies the following conditions:
In a valid orientation, a cable is considered cut if one of the lasers intersects its interior, that is, the segment without its endpoints. Each cut cable contributes its value $$$w_i$$$; cables that are not cut contribute nothing.
Find the maximum total value that can be obtained with a valid orientation. If there is none, print $$$-1$$$.
It is not necessary to cut all the cables, or even one. However, if both lasers intersect the same cable, the whole orientation is invalid: you cannot simply discard that cable from the score.
It is guaranteed that no cable contains the origin. Cables may cross, share endpoints or overlap; they are considered independent objects and their values are counted separately.
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^{4}$$$), the number of test cases.
For each test case:
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \times 10^{5}$$$), the number of cables.
Each of the following $$$n$$$ lines contains five integers:
$$$$$$x_{i,1}\quad y_{i,1}\quad x_{i,2}\quad y_{i,2}\quad w_i$$$$$$
with the constraints
$$$$$$-10^{9}\le x_{i,1},y_{i,1},x_{i,2},y_{i,2}\le 10^{9},$$$$$$
$$$$$$1\le w_i\le 10^{9}.$$$$$$
The endpoints of each cable are distinct and the segment joining them does not contain $$$(0,0)$$$.
The sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^{5}$$$.
For each test case, print an integer: the maximum total value of the cut cables with a valid orientation, or $$$-1$$$ if there is no valid orientation.
434 1 4 2 51 4 2 4 73 1 1 3 42-2 1 2 1 53 2 2 3 1003-3 -2 3 -2 13 -2 1 4 11 4 -3 -2 111 1 2 2 9
11 5 -1 0
Explanation for example 1
In the first case, the lines $$$y=\frac52x$$$ and $$$y=-\frac25x$$$ form a valid orientation. The second and third cables are cut, obtaining $$$7+4=11$$$. There is no valid orientation that achieves a larger value.
In the second case, the coordinate axes form a valid orientation that cuts only the first cable, obtaining $$$5$$$. Any orientation that cuts the cable of value $$$100$$$ intersects the first cable with both lasers, so it is invalid.
In the third case, the cables form the outline of a triangle that contains the origin in its interior. Every line through the origin that avoids the vertices crosses two sides. Between the two lasers there are four intersections with only three cables, so at least one of them receives two cuts. There is no valid orientation.
In the fourth case, the cable lies on the same ray that starts at the origin and passes through $$$(1,1)$$$. A line through the origin can only cut it if it also passes through its endpoints, which is forbidden. Valid orientations exist, but none of them cuts the cable; the answer is $$$0$$$.
