eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Магазин конфет

Магазин конфет

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Прогуливаясь с другом, Вы случайно проходите мимо кондитерской. Насколько нездоровыми являются сладости! Каждый из Вас заходит в магазин с одинаковым количеством денег. Тот, кто купит конфет с наибольшим общим количеством калорий, побеждает.

Поскольку Вы умный ученый, то у Вас имеется доступ к товарам кондитерской. Вы решили написать программу, которая определит наибольшее количество калорий, которое можно купить. Для каждого товара известна цена и число калорий. Каждого товара достаточно в наличии, поэтому Вы можете купить любое его количество. Купить можно только целое количество конфет.

Вхідні дані

Состоит из нескольких тестов. Первая строка каждого теста содержит количество различных типов конфет 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 долларов включительно.

Приклад

Вхідні дані #1
2 8.00
700 7.00
199 2.00
3 8.00
700 7.00
299 3.00
499 5.00
0 0.00
Вихідні дані #1
796
798