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}$.

제한

힌트