Шоу талантов
Фермер Джон привёл n своих коров, последовательно пронумерованных 1..n, на ярмарку, где проводится соревнование талантливых коров. Его i-ая корова имеет вес w[i] уровень таланта t[i] - оба целые числа.
Сразу по прибытии ФД был удивлён новыми правилами соревнования:
(i) Должна участвовать группа коров весом не менее W
(ii) Группа с наибольшим коэффициентом отношения таланта к весу побеждает.
ФД заметил, что все его коровы вместе весят не менее W, поэтому он легко удовлетворит условие (i). Помогите ему определить наивысший коэффициент отношения таланта к весу для любой из его команд.
Входные данные
Первая строка ввода содержит n (1 ≤ n ≤ 250) и W (1 ≤ W ≤ 1000). Каждая из следующих n строк описывает корову двумя целыми числами w[i] (1 ≤ w[i] ≤ 10^6) и t[i] (1 ≤ t[i] ≤ 1000).
Выходные данные
Определите наибольший возможный коэффициент отношения таланта к весу для групп ФД весом не менее w. Если Ваш ответ A, выведите целую часть от 1000A, чтобы ответ получился целым числом. Дробная часть результата отбрасывается, с округлением вниз до целого, если число не целое.
Пример
В этом примере наилучший коэффициент достигает одной коровой с талантом 11 и весом 10, но поскольку требуется вес не менее 15, оптимальное решение задачи использовать корову 10 11 и корову 20 21. Получится коэффициент таланта к весу (11 + 21) / (10 + 20) = 32 / 30 = 1.0666666..., который умножается на 1000 и при отбрасывании дробной части получается 1066.