Farmer John zabiera $N$ krów numerowanych $1\ldots N$ na coroczny pokaz talentów na targach hrabstwa. Krowa $i$ ma całkowitą wagę $w_i$ i talent $t_i$.

Nowe zasady go zaskakują:

(i) Grupa musi ważyć co najmniej $W$, aby rywalizowały silne zespoły, a nie tylko silne jednostki.

(ii) Wygrywa grupa o największym stosunku sumy talentu do sumy wagi.

Wszystkie krowy ważą co najmniej $W$, więc (i) jest możliwe. Znajdź najlepszy stosunek dla takiego zespołu.

Wejście

Pierwszy wiersz zawiera $N$ ($1 \leq N \leq 250$) i $W$ ($1 \leq W \leq 1000$). Następne $N$ wierszy podaje liczby całkowite $w_i$ ($1 \leq w_i \leq 10^6$) i $t_i$ ($1 \leq t_i \leq 10^3$).

Wyjście

Znajdź maksimum przy wadze co najmniej $W$. Jeśli to $A$, wypisz podłogę $1000A$, aby wynik był całkowity; podłoga odrzuca część ułamkową, zaokrąglając w dół, jeśli liczba nie jest całkowita.

Przykład

Wejście 1

3 15
20 21
10 11
30 31

Wyjście 1

1066

Uwagi

Talent 11 i waga 10 jest najlepsza sama, ale trzeba wagi 15, więc dodaje się talent 21 i wagę 20. $(11+21)/(10+20)=32/30=1.0666666...$ razy 1000 i zaokrąglone w dół daje 1066.

Autor zadania: Brian Dean