Fractional Knapsack

Each item is a pair [value, weight]. A bag holds total weight at most capacity. You may take a fraction of an item (half the weight gives half the value). Return the largest total value you can carry, as a number (answers within 1e-9 are accepted).

For items = [[60, 10], [100, 20], [120, 30]] and capacity = 50 the answer is 240.0.

Examples

Example 1

Input:

fractional_knapsack([[60, 10], [100, 20], [120, 30]], 50)

Output:

240.0

Example 2

Input:

fractional_knapsack([[500, 30]], 10)

Output:

166.66666666666666

Constraints

• 0 <= len(items) <= 200000
• 1 <= value, weight <= 1000
• 0 <= capacity <= 10**6