favorite We need a little bit of your help to keep things running, click on this banner to learn more

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.


In the first line two values n and w (1n1000, 1w106) 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.


Print the desired maximum cost with 3 digits after the decimal point.

Time limit 1 second
Memory limit 64 MiB
Input example #1
3 50
60 20
100 50
120 30
Output example #1