21073번 - Final Exam 스페셜 저지다국어

Rikka is a talented student.

She spends almost every day on ICPC. But the final exam is approaching. 

Rikka plans to grasp- the last minute to review the courses before the exam. She has up to $M$ minutes for review and then takes $n$ consecutive exams. If Rikka spends $x$ minutes on the review for the $i$-th exam, she would get $f_i (x)$ points, where $f_i (x) = \max \{0, \min \{d_i, a_i x^2 + b_i x + c_i\}\}$ with the exam-specific parameters $a_i, b_i, c_i, d_i$.

Rikka wants to maximize the total score of her $n$ exams. Note the minutes she spends in reviewing a certain course can be any non-negative real number. Also, she does not have to spend all of her $M$ minutes on the review so that she can spend more time on ICPC.

The first line contains an integer $n$ and a real number $M$.

Each of the following $n$ lines contains four real numbers $a_i, b_i, c_i, d_i$, denoting the parameters of all the $n$ exams.

It is guaranteed that $1 \le n \le 100\,000$, $0 < M \le 10^8$, $|a_i| \le 10$, $|b_i| \le 5000$, $0 \le c_i \le d_i \le 5000$, and all real numbers in the input are given with exactly three decimal places.

It is guaranteed that there are at most $18$ exams with $a_i > 0$.

You need to output $d$, the maximum total score that Rikka can get. Assuming the correct result is $d^*$, you need to ensure that $\frac{|d - d^*|}{\max\{d^*, 1\}} \leq 10^{-6}$.