Магазин конфет
Магазин конфет
Прогуливаясь с другом, Вы случайно проходите мимо кондитерской. Насколько нездоровыми являются сладости! Каждый из Вас заходит в магазин с одинаковым количеством денег. Тот, кто купит конфет с наибольшим общим количеством калорий, побеждает.
Поскольку Вы умный ученый, то у Вас имеется доступ к товарам кондитерской. Вы решили написать программу, которая определит наибольшее количество калорий, которое можно купить. Для каждого товара известна цена и число калорий. Каждого товара достаточно в наличии, поэтому Вы можете купить любое его количество. Купить можно только целое количество конфет.
Вхідні дані
Состоит из нескольких тестов. Первая строка каждого теста содержит количество различных типов конфет n\:(1 \le n \le 5000) и количество денег m\:(0.01 \le m \le 100.00), которое Вы можете потратить. Количество денег m выражается в долларах с двумя десятичными знаками без ведущих нулей, кроме случая когда сумма меньше доллара. Каждая из следующих n строк содержит целое число c\:(1 \le c \le 5000) и количество денег p\:(0.01 \le p \le 100.00). Здесь c — количество калорий одной единицы товара, а p — ее цена в долларах в том же формате что и m. Последняя строка содержит 0\:0.00 и не обрабатывается.
Вихідні дані
Для каждого теста выведите в отдельной строке наибольшее количество калорий, которое можно купить на сумму до m долларов включительно.
Приклад
2 8.00 700 7.00 199 2.00 3 8.00 700 7.00 299 3.00 499 5.00 0 0.00
796 798