Knapsack - Рюкзак
Golden sand
During robbery in a store a thief found n boxes with golden sand. All the sand in a box under the number i has cost vi
and weight wi
. To carry the stolen, the thief uses a knapsack. Determine the highest total cost of sand that can carry out the robber, if knapsack capacity is limited to w.
One can pour from boxes any amount of sand, while the ratio of the cost of the poured sand to the cost of the entire box is equal to the ratio of volume of the poured sand to the volume of entire sand box.
Input
In the first line two values n and w (1 ≤ n ≤ 1000, 1 ≤ w ≤ 106
) are given. Each of the next n lines contains two integers. The i-th line contains the price vi
and weight wi
of the sand at i-th box. All numbers are non-negative and do not exceed 106
.
Output
Print the desired maximum cost with 3 digits after the decimal point.
3 50 60 20 100 50 120 30
180.000