Hide

Problem F
Bastubad

Languages en ja sv
/problems/bastubad/file/statement/sv/img-0001.jpg
Picture by SM (cc-by-sa3.0)
Finländare älskar att bada bastu. Det är inte så konstigt egentligen. Bastubadande är både skönt och sker oftast i trevligt sällskap.

I sällskap uppstår dock ofta problem. Det viktigaste när man badar bastu är att temperaturen sätts rätt. En finländare är väldigt petig med bastuns temperatur. Olika finländare har olika högstatemperaturer som de tolererar. Om temperaturen är för hög för en viss finländare så går finländaren hem. I temperaturintervallet som en viss finländare klarar blir finländaren dessutom olika glad beroende på temperaturen. En finländares glädje ges av en kvadratisk funktion (på formen $ax^2 + bx + c$).

Ett stort sällskap finländare ska nu bada bastu, och behöver din hjälp. Kan du bestämma den maximala summan av finländarnas glädje, om bastuns temperatur sätts optimalt? Om temperaturen sätts högre än vad en finne tolererar, så bidrar inte denna finne till den totala glädjen alls (den har ju gått hem). Temperaturen anges i kelvin, med en undre gräns på $0 \textrm{ K}$ och övre gräns $100\, 000 \textrm{ K}$.

Indata

Den första raden innehåller ett heltal $1 \le N \le 100\, 000$: antalet finländare. Därefter följer $N$ rader, en per finländare. Varje rad innehåller fyra heltal $a, b, c, t$ ($-10^9 \le a,b,c \le 10^9, 1 \le t \le 100\, 000$), vilket representerar att finländaren har glädjefunktion $ax^2 + bx + c$, and bara klarar av temperaturer mellan $0\textrm{ K}$ och $t\textrm{ K}$, inklusive. Funktionen garanteras vara positiv överallt mellan $0$ och $t$.

Utdata

Skriv ut ett enda tal: den största möjliga lycka som kan uppnås om temperaturen sätts rätt. Svaret kommer accepteras om det har ett relativt eller absolut fel om högst $10^{-5}$.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp

Poängvärde

Gränser

$1$

$21$

$N \le 1000$, alla $t$ är samma.

$2$

$29$

$N \le 1000$, alla $a$ är positiva (d.v.s., finnarna gillar temperaturextremer).

$3$

$38$

$N \le 1000$, alla $a$ är negativa.

$4$

$12$

Inga begränsningar.

Förklaring av exempel $1$

I detta fall är den optimala temperaturen $0 \textrm{ K}$. Båda finnar har i detta fall samma glädje: $1 \cdot 0^2 -6\cdot 0 + 10 = 10$. Deras totala glädje blir $10 + 10 = 20$.

Förklaring av exempel $2$

I detta fall är den optimala temperaturen $\frac{10}{3} \textrm{ K}$. Den första finnens lycka blir $-3(\frac{10}{3})^2 + 20 \cdot \frac{10}{3} + 3 = -\frac{100}{3} + \frac{200}{3} + 3 = 36 + \frac{1}{3}$. Den andra finnen går i detta fallet hem för att temperaturen är för hög (hon tolererar bara temperaturer upp till $1\textrm{ K}$). Den totala lyckan blir därmed $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