Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

問題文

実数変数 x1,x2,...,xN は以下の条件を満たす。

  1. 0xi1 (1iN)
  2. w1x1+w2x2+...+wNxNW

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

入力

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

N W
w1 v1
w2 v2
...
wN vN

制約

出力

v1x1+v2x2+...+vNxN のとりうる最大値を1行に出力せよ。 出力には 103 を超える誤差があってはならない。

Sample Input 1

1 1
3 1

Output for the Sample Input 1

0.333333

x1=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