#arc072d. [arc072_d]Dam

[arc072_d]Dam

問題文

あなたはダムを管理しています。ダムは LL リットルまで水を蓄えることができます。ダムははじめ干からびています。また、毎日夜に好きな量の水を排出することができます。毎日朝にはダムに水が流入しますが、その時水が溢れないようにする必要があります。

ii 日目の朝には tit_i 度の水が viv_i リットル流入することがわかっています。 各日について、あなたはその日の昼にダムにちょうど LL リットルの水がたまっているという条件のもと、その時点でのダムの水温を最大化しようとすると何度になるかふと気になりました。各 ii について水温の最大値を求めてください。ここで、各最大化のための水の排出は独立に考えるものとします。すなわち、ii 日目の水温の最大化のために排出する水の量は、j(i)j(≠i) 日目の水温の最大化のために排出する水の量と異なっていても構いません。

ただし、水温は流れてくる水以外の一切の影響を受けないものとします。特に、T1T_1 度、V1V_1 リットルの水と T2T_2 度、V2V_2 リットルの水が混ざると fracT1\*V1+T2\*V2V1+V2\\frac{T_1\*V_1+T_2\*V_2}{V_1+V_2} 度、V1+V2V_1+V_2 リットルの水となり、これ以外で水の体積・温度が変化することはありません。

制約

  • 1N5\*1051≦ N ≦ 5\*10^5
  • 1L1091≦ L ≦ 10^9
  • 0ti109(1iN)0≦ t_i ≦ 10^9(1≦i≦N)
  • 1viL(1iN)1≦ v_i ≦ L(1≦i≦N)
  • v1=Lv_1 = L
  • L,vi,tiL, v_i, t_i は整数である

入力

入力は以下の形式で標準入力から与えられる。

NN LL t1t_1 v1v_1 t2t_2 v2v_2 : tNt_N vNv_N

出力

ii 日目の朝にダムに LL リットル蓄えることのできる水温の最大値を ii 行目に出力せよ。

答えは、相対誤差または絶対誤差が 10610^{-6} 以下であれば許容される。


入力例 1

3 10
10 10
20 5
4 3

出力例 1

10.0000000
15.0000000
13.2000000
  • 11 日目には 11 日目に流れ込んだ水のみがあるので、必ず1010度です。
  • 11 日目の夜に水を 55 リットル捨て、22 日目に流入する水と混ざると 1010 リットル、1515 度の水が 22 日目に蓄えられます。
  • 11 日目の夜に水を 88 リットル捨て、2,32, 3 日目に流入する水と混ざると 1010 リットル、13.213.2度の水が 33 日目に蓄えられます。

入力例 2

4 15
0 15
2 5
3 6
4 4

出力例 2

0.0000000
0.6666667
1.8666667
2.9333333

入力例 3

4 15
1000000000 15
9 5
8 6
7 4

出力例 3

1000000000.0000000
666666669.6666666
400000005.0000000
293333338.8666667

水温は 100100 度を超えることがありますが、蒸発については考えません。