Golden sand#3736
There are boxes containing golden sand samples. The sand in the -th box has a total value of v_i and a total weight of w_i. You have a bag (knapsack) with a capacity limit of . Determine the highest total value of sand you can take if you may collect any fraction of sand from any box, as long as the ratio of value taken to the full box value equals the ratio of weight taken to the full box weight.
The first line contains two integers and (1 \leq n \leq 1000, 1 \leq w \leq 10^6). Each of the next lines contains two integers: the value v_i and weight w_i of sand in the -th box. All numbers are non-negative and do not exceed 10^6.
Print the maximum total value with digits after the decimal point.
Ejemplo 1