Fractional knapsack
Given
n items with their weights and values, you would like to put those items in a knapsack of capacity W to get the maximum total value in your knapsack. You’re allowed to take some fraction (part) of an item, in which case the price changes proportionally to the fraction you’ve taken.What would be the maximum total value of the knapsack?
Input
The first line of the input contains two integers
n (1 ≤ n ≤ ) the number of items, and W (1 ≤ W ≤ ) the capacity of your knapsack.The next
n lines contain space-separated pairs of integers Output
The program should print the maximum total value of the knapsack.
Examples
Input | Output |
3 50
10 60
20 100
30 120 | 240 |
4 60
40 280
10 100
20 120
24 120 | 440 |
Explanation
- 60 + 100 + (2/3)120 = 240
- 280 + 100 + (10/20)120 = 440
Constraints
Time limit: 0.2 seconds
Memory limit: 512 MB
Output limit: 1 MB