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