Flyga Drönare

Du har just fått en ny batteridriven drönare, men saknar batterier. I affären finns det $N$ batterier tillgängliga till drönaren, som vardera har en energi $e_ i$, vikt $w_ i$ och kostnad $c_ i$. Butiken har endast ett exemplar av varje batteri.

För att kunna ha så kul som möjligt med drönaren vill du såklart att den ska flyga så länge som möjligt på en full laddning. Tiden drönaren kan vara i luften ges av uttrycket $t = \frac{E_{tot}}{W_{tot}}$ där $E_{tot}$ är det totala energi-innehållet för alla drönarens batterier, och $W_{tot}$ är den kombinerade vikten av drönaren och batterierna.

Givet en budget $B$ samt en vikt på drönaren själv $W$, bestäm det maximala tiden drönaren kan flyga.

Indata

Den första raden innehåller tre heltal $N$, $B$ och $W$ ($1 \le N\times B \le 200\, 000$ och $1\le W \le 1000$) – antal tillgängliga batterier, din budget och drönarens vikt.

Därefter följer $N$ rader med tre heltal. Rad nummer i innehåller $e_ i$, $w_ i$ och $c_ i$ ($0 \le e_ i \le 1000$, $0 \le w_ i \le 1000$, $0 \le c_ i \le B$) – energin, vikten, samt kostnaden för batteri $i$.

Utdata

Skriv ut ett decimaltal – Det längsta tiden du kan flyga din drönare om du väljer batterier rätt. Svaret kommer accepteras om det har ett relativt eller absolut fel om högst $10^{-5}$. Dvs, om ditt svar är $a$ och det korrekta svaret är $b$, så accepteras ditt svar om antingen $|a-b| \le 10^{-5}$ eller $\frac{|a-b|}{|b|} \le 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$

$10$

$N \leq 20$

$2$

$20$

$w_ i = 0$

$3$

$20$

$c_1 = c_2 = ... = c_ N$

$4$

$50$

inga ytterligare begränsningar

Exempelfall

Sample Input 1 Sample Output 1
10 1000 20
40 40 40
1 1 1
70 30 60
100 20 700
80 50 200
30 1 200
100 100 1
20 1 500
30 20 100
70 50 100
3.17073170731707