問題文
実数変数 $x_1, x_2, ..., x_N$ は以下の条件を満たす。
- $0 \leq x_i \leq 1$ ($1 \leq i \leq N$)
- $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