Шоу талантів
Фермер Джон привів 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.