Farmer John bringt $N$ Kühe, nummeriert $1\ldots N$, zur jährlichen Kuhtalentschau auf dem Jahrmarkt des Bezirks. Kuh $i$ hat ganzzahliges Gewicht $w_i$ und Talent $t_i$.

Die neuen Regeln überraschen ihn:

(i) Eine Gruppe muss mindestens $W$ wiegen, damit starke Teams und nicht nur starke Einzeltiere antreten.

(ii) Die Gruppe mit dem höchsten Verhältnis von Gesamttalent zu Gesamtgewicht gewinnt.

Alle Kühe zusammen wiegen mindestens $W$, daher ist (i) erfüllbar. Bestimme das beste Verhältnis für solch ein Team.

Eingabe

Die erste Zeile enthält $N$ ($1 \leq N \leq 250$) und $W$ ($1 \leq W \leq 1000$). Die nächsten $N$ Zeilen geben ganze Zahlen $w_i$ ($1 \leq w_i \leq 10^6$) und $t_i$ ($1 \leq t_i \leq 10^3$) an.

Ausgabe

Bestimme das maximale Verhältnis bei Gewicht mindestens $W$. Ist es $A$, gib die abgerundete Zahl $1000A$ aus, damit das Ergebnis ganzzahlig ist. Abrunden verwirft den Bruchteil einer nichtganzen Zahl.

Beispiele

Eingabe 1

3 15
20 21
10 11
30 31

Ausgabe 1

1066

Hinweis

Talent 11 und Gewicht 10 wäre allein am besten, aber Gewicht 15 ist nötig. Daher kommt die Kuh mit Talent 21 und Gewicht 20 hinzu. $(11+21)/(10+20)=32/30=1.0666666...$, mal 1000 und abgerundet, ergibt 1066.

Aufgabenautor: Brian Dean