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 (1 β€ , β€ ) the weight and the value of each item.
Output
The program should print the maximum total value of the knapsack.