Fractional Knapsack

Time Limit : 1 sec, Memory Limit : 65536 KB

問題文

実数変数 x_1, x_2, ..., x_N は以下の条件を満たす。

  1. 0 \leq x_i \leq 1 (1 \leq i \leq N)
  2. w_1x_1+w_2x_2+...+w_Nx_N \leq W

このとき v_1x_1+v_2x_2+...+v_Nx_N のとりうる最大値を求めよ。そのような最大値は実際に存在することが知られている。

入力

入力は以下の形式に従う。与えられる数は全て整数である。

N W
w_1 v_1
w_2 v_2
...
w_N v_N

制約

  • 1 \leq N \leq 10^5
  • 1 \leq W \leq 10^5
  • -10^4 \leq w_i \leq 10^4
  • -10^4 \leq v_i \leq 10^4

出力

v_1x_1+v_2x_2+...+v_Nx_N のとりうる最大値を1行に出力せよ。 出力には 10^{-3} を超える誤差があってはならない。

Sample Input 1

1 1
3 1

Output for the Sample Input 1

0.333333

x_1=1/3 のとき最大となる。

Sample Input 2

2 3
3 3
1 2

Output for the Sample Input 2

4.000000

Sample Input 3

2 1
-1 -3
3 10

Output for the Sample Input 3

3.666667

Source: Osaka University Programming Contest 2012 , Osaka, Japan, 2012-03-18