e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin köməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Məsələlər

Золотой песок

Золотой песок

Во время ограбления магазина вор обнаружил n ящичков с золотым песком. Весь песок в ящичке под номером i имеет стоимость vi и вес wi. Чтобы унести награбленное, вор использует рюкзак. Требуется определить наибольшую суммарную стоимость песка, который может унести грабитель, если грузоподъёмность рюкзака ограничена величиной w.

Из ящичков можно пересыпать любое количество песка, тогда отношение стоимости отсыпанного песка к стоимости всего ящика будет равно отношению объёма отсыпанного песка к объёму всего ящика.

Входные данные

В первой строке записаны два числа n и w (1 n 1000, 1 w 106). Далее следует n строк по два целых числа в каждой. В i-ой строке записана стоимость vi и вес wi песка в i-ом ящике. Все числа неотрицательные и не превосходят 106.

Выходные данные

Выведите искомую максимальную стоимость с точностью до 3 знаков после запятой.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
3 50
60 20
100 50
120 30
Çıxış verilənləri #1
180.000