Доработайте программу таким образом, чтобы она решала следующую задачу.
Во время ограбления магазина вор обнаружил N
ящичков с золотым песком. В ящичек под номером i
песок имеет стоимость vi
и вес wi
. Чтобы унести награбленное, вор использует рюкзак. Требуется определить наибольшую суммарную стоимость песка, который может унести грабитель, если грузоподъемность рюкзака ограничена величиной W.
Из ящичков можно пересыпать любое количество песка. Тогда отношение стоимости отсыпанного песка к стоимости всего ящичка будет равна отношению объема пересыпанного песка к объему всего ящичка.
Входные данные
В первой строке входного файла записаны два числа - N
и W
(1 <= N <= 1000, 0 <= W <= 1000000). Далее следует N
строк по два целых числа в каждой. В i
-ой строке записана стоимость vi
и вес wi
песка в i
-ом ящичке. Все числа неотрицательные и не превосходят 106.
Выходные данные
Выведите искомую максимальную стоимость с погрешностью не более 0,0001.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
3 50
60 20
100 50
120 30
|
180.0000 |