Магазин цукерок#6210

Магазин цукерок

1 секунда

128 мегабайтів

Дуже легка

Гуляючи з другом, ви випадково проходите повз магазин цукерок. Які ж вони шкідливі! Кожен з вас заходить до магазину з однаковою сумою грошей. Хто купить цукерок із найбільшою загальною кількістю калорій, той перемагає.

Оскільки ви розумний науковець, у вас є доступ до асортименту кондитерської. Ви вирішуєте написати програму, яка визначить максимальну кількість калорій, яку можна придбати. Для кожного товару відома ціна та кількість калорій. Кожного товару у магазині необмежена кількість, тож ви можете придбати скільки завгодно. Можна купувати лише цілу кількість цукерок.

Вхідні дані

Вхід складається з декількох тестових випадків. У першому рядку кожного тесту задано кількість різних видів цукерок $n$ ( $1 \leq n \leq 5000$ 1 \le n \le 5000) та суму грошей $m$ ( $0.01 \leq m \leq 100.00$ 0.01 \le m \le 100.00), яку ви можете витратити. Сума грошей $m$ записується у доларах з двома десятковими знаками та без початкових нулів, окрім випадків, коли сума менша за долар. Кожен із наступних $n$ рядків містить ціле число $c$ ( $1 \leq c \leq 5000$ 1 \le c \le 5000) та суму грошей $p$ ( $0.01 \leq p \leq 100.00$ 0.01 \le p \le 100.00). Тут $c$ — кількість калорій в одному виробі, а $p$ — його ціна у доларах у тому ж форматі, що і $m$ . Останній рядок містить $0$ $0.00$ і не підлягає обробці.

Вихідні дані

Для кожного тесту виведіть в окремому рядку максимальну кількість калорій, яку можна придбати на суму до $m$ доларів включно.

Приклади

Приклад 1