問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
氷の世界に来た paiza 君は、荷物を氷の上で輸送する仕事をすることになりました。
今回の仕事では、x 座標 0 から L まで、x 軸上で荷物を滑らせて輸送をおこないます。ここで、座標での距離 1 を 1 メートルとします。
この氷に摩擦はなく、滑らせた荷物は等速直線運動をします。
ところが、paiza 君が入念に調査したところ、輸送路の途中、x 座標 l_1, l_2, ..., l_n には亀裂があり、それぞれ荷物の速度を r_1, r_2, ..., r_n (メートル毎秒) だけ減速させることがわかりました。
輸送には制限時間があり、この仕事は t 秒以内に終わらせなければなりません。
輸送を t 秒以内に終わらせるためには、初速度を何メートル毎秒以上にする必要があるか求めてください。
ただし、ある地点での減速後の速度が負になってしまう場合は、輸送ができないものとします。
n t
l_1 r_1
l_2 r_2
...
l_n r_n
L
輸送を t 秒以内に終わらせるためには、初速度を何メートル毎秒以上にする必要があるかを表す小数を一行で出力してください。
また、末尾に改行を入れ、余計な文字を含んではいけません。
相対誤差または絶対誤差が 10^-6 以下であれば正解とみなします。
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 1 ≦ n ≦ 100000 = 10^5
・ 1 ≦ t ≦ 100000 = 10^5
・ 0 < l_1 < l_2 < ... < l_n < L ≦ 1000000000 = 10^9
・ 1 ≦ r_i ≦ 100000 = 10^5 (1 ≦ i ≦ n)
2 4
4 2
6 1
8
4