Farmer John привёз $N$ коров, пронумерованных $1\ldots N$, на ежегодное шоу талантов окружной ярмарки. Вес $w_i$ и талант $t_i$ коровы $i$ целые.

Новые правила удивили его:

(i) Надо выставить группу суммарного веса хотя бы $W$, чтобы соревновались сильные команды, а не только отдельные коровы.

(ii) Побеждает группа с максимальным отношением суммарного таланта к суммарному весу.

Вес всех коров хотя бы $W$, значит (i) выполнимо. Найдите максимальное достижимое отношение.

Входные данные

Первая строка содержит $N$ ($1 \leq N \leq 250$) и $W$ ($1 \leq W \leq 1000$). Следующие $N$ строк задают коров целыми $w_i$ ($1 \leq w_i \leq 10^6$) и $t_i$ ($1 \leq t_i \leq 10^3$).

Выходные данные

Найдите максимальное отношение для веса хотя бы $W$. Если ответ $A$, выведите округлённое вниз $1000A$, чтобы ответ был целым. Округление вниз отбрасывает дробную часть нецелого числа.

Примеры

Входные данные 1

3 15
20 21
10 11
30 31

Выходные данные 1

1066

Примечание

Лучшее отношение у коровы с талантом 11 и весом 10, но нужен вес 15, поэтому берут также талант 21, вес 20. $(11+21)/(10+20)=32/30=1.0666666...$ после умножения на 1000 и округления вниз даёт 1066.

Автор задачи: Brian Dean