Олимпиадный тренинг

Задача . Песок


Задача

Темы:
Доработайте программу таким образом, чтобы она решала следующую задачу.

Во время ограбления магазина вор обнаружил 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

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6471
Комментарий учителя