Hide

Problem H
Saunas

/problems/bastubad/file/statement/en/img-0001.jpg
Picture by SM (cc-by-sa3.0)
Finns love to use saunas. It’s actually not so strange. Sauna bathing feels good and usually takes place among good company.

However, problems often occur when there is company. The most important thing when one uses a sauna is that the temperature is set correctly. A Finn can be really fussy about a sauna’s temperature. Different Finns have different maximum temperatures that they tolerate. If the temperature is too high for a particular Finn, that Finn will go home. Within the temperature range that a particular Finn can handle, that Finn has a different level of happiness depending on the temperature. A Finn’s happiness follows a quadratic function (of the form $ax^2 + bx + c$).

A large number of Finns are using the sauna and they need your help. Can you find the maximum sum of the Finns’ happiness if the sauna’s temperature is set optimally? If the temperature is set higher than a Finn can tolerate, that Finn contributes nothing to the total happiness (they have gone home instead). The temperature is given in kelvin, with a lower bound of $0 \textrm{ K}$ and an upper bound of $100\, 000 \textrm{ K}$.

Input

The first line contains an integer $1 \le N \le 100\, 000$, which is the number of Finns. After that follow $N$ lines, one per Finn. Each line contains four integers $a, b, c$, and $t$ ($-10^9 \le a,b,c \le 10^9, 1 \le t \le 100\, 000$), which represent that the Finn has happiness function $ax^2 + bx + c$, and can only handle temperatures between $0 \textrm{ K}$ and $t\textrm{ K}$, inclusive. The function is guaranteed to be positive over all values between $0$ and $t$.

Output

Write out a single number: the largest possible happiness that can be achieved if the temperature is set correctly. The answer will be accepted if it has a relative or absolute error of at most $10^{-5}$.

Points

Your solution will be tested on several test case groups. To get points for a group, your solution must pass all the test cases in the group.

Group

Point value

Bounds

$1$

$21$

$N \le 1000$, all $t$ are the same.

$2$

$29$

$N \le 1000$, all $a$ are positive (i.e., the Finns love extreme temperatures).

$3$

$38$

$N \le 1000$, all $a$ are negative.

$4$

$12$

No additional constraints.

Explanation of example $1$

In this case the optimal temperature is $0 \textrm{ K}$. Both Finns have the same happiness in this case: $1 \cdot 0^2 - 6 \cdot 0 + 10 = 10$. Their total happiness is $10 + 10 = 20$.

Explanation of example $2$

In this case the optimal temperature is $\frac{10}{3} \textrm{ K}$. The first Finn’s happiness is $-3(\frac{10}{3})^2 + 20 \cdot \frac{10}{3} + 3 = -\frac{100}{3} + \frac{200}{3} + 3 = 36 + \frac{1}{3}$. The second Finn in this case goes home, because the temperature is too high (she only tolerates temperatures up to $1\textrm{ K}$). The total happiness is therefore $36 + \frac{1}{3}$.

Sample Input 1 Sample Output 1
2
1 -6 10 4
1 -6 10 7
20.0000000000
Sample Input 2 Sample Output 2
2
-3 20 3 5
-1 0 2 1
36.3333333333
Sample Input 3 Sample Output 3
1
1000000 2 3 10000
100000000020003.0000000000

Please log in to submit a solution to this problem

Log in