Fractional Knapsack Problem

Fractional Knapsack Problem

Given item weights, values, and a knapsack capacity, maximize value when items can be split.

Input format

The first line contains N and CAP. The second line contains N weights. The third line contains N values.

Output format

Print the maximum value (floor) achievable with fractional knapsack.

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

9 20
4 2 9 4 2 1 9 8 2
8 14 18 32 12 8 54 8 2

124

7 48
1 4 10 5 3 4 4
3 24 30 5 3 16 32

113