n человек стоят на координатной прямой в точках с положительными целочисленными координатами, строго меньшими 106. Для каждого человека известно, в какую сторону он смотрит (влево или вправо), и его максимальная скорость.
У вас есть возможность разместить одну бомбу в точку с целочисленной неотрицательной координатой, и взорвать ее. В этот момент все люди побегут со своей максимальной скоростью в те стороны, в которые они смотрят, а от бомбы начнут распространяться два странных луча со скоростью s: влево и вправо. Конечно, скорость лучей s строго больше скорости любого человека.
Странность лучей в том, что в момент, когда положение некоторого луча и его направление совпадает с положением и направлением бега некоторого человека, скорость этого человека увеличивается на скорость луча.
Требуется положить бомбу в такое место, чтобы минимальный момент времени, в который и мимо точки 0, и мимо точки 106 пробежал хотя бы один человек, был как можно меньше. Иными словами, найдите минимальный момент времени t такой, что существует точка, в которую можно положить бомбу так, чтобы в момент времени t и мимо точки 0, и мимо точки 106 кто-то пробежал.
Выходные данные
Выведите минимальное время, за которое могут быть достигнуты обе точки 0 и 106.
Ваш ответ будет считаться правильным, если его абсолютная или относительная точность не превосходит 10 - 6. А именно, если ваш ответ равен a, а ответ жюри равен b, то ваш ответ будет зачтен, если 
.
Примечание
В первом примере оптимально поставить бомбу в точке с координатой 400000. Тогда в момент времени 0 скорость первого станет 1000 и он достигнет точки 106 в момент времени 600. На второго человека бомба не повлияет и он достигнет точки 0 в момент времени 500000.
Во втором примере оптимально поставить бомбу в точке с координатой 500000. Лучи догонят обоих людей в момент времени 200. В этот момент первый находится в точке с координатой 300000, а второй 700000. Их скорость станет равна 1500 и в момент времени 400 они одновременно пересекут точки 0 и 106.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 999
400000 1 2
500000 1 1
|
500000.000000000000000000000000000000
|
|
2
|
2 1000
400000 500 1
600000 500 2
|
400.000000000000000000000000000000
|