分割可能ナップサック (Fractional Knapsack)

n 個の品物があり、それぞれの品物には重さと価値が定められています。容量 W のナップサックに品物を詰め込み、ナップサックの合計価値を最大化したいとします。このとき、品物を部分的に(ある割合だけ)取り出すことも可能で、その割合に比例して価値も変動します。

このナップサックに詰められる合計価値の最大値は、いくらになるでしょうか?

入力

最初の行には、品物の数を示す整数 n (1 ≤ n ≤ ) と、ナップサックの容量を示す整数 W (1 ≤ W ≤ ) が与えられます。

続く n 行では、各品物の重さと価値を表す整数 (1 ≤ , ) が、スペース区切りで与えられます。

出力

ナップサックに詰めたときの最大の合計価値を出力してください。

入力

出力

3 50
10 60
20 100
30 120

240

4 60
40 280
10 100
20 120
24 120

440

説明

  1. 60 + 100 + (2/3)120 = 240

  2. 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