Algorithms and Data Structures

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 (1 ≤ , ≤ ) the weight and the value of each item.

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

  1. 60 + 100 + (2/3)120 = 240
  1. 280 + 100 + (10/20)120 = 440
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue