В аэропортах часто используются траволаторы, потому что они помогают проходить большие расстояния быстрее. Каждый траволатор имеет некоторую собственную скорость, которая увеличивает скорость, с которой вы идёте. Вы можете просто стоять на траволаторе (тогда вы будете двигаться со скоростью траволатора), либо вы можете ещё и идти, тогда ваша итоговая скорость будет равна сумме скорости, с который вы идёте, и скорости траволатора.
Лимак хочет добраться из точки $$$0$$$ в точку $$$L$$$, расположенные на одной прямой. Между ними есть $$$n$$$ дизъюнктных траволаторов. $$$i$$$-й из них описывается целыми числами $$$x_i$$$, $$$y_i$$$ и вещественным числом $$$s_i$$$. $$$i$$$-й траволатор начинается в $$$x_i$$$, заканчивается в $$$y_i$$$ и имеет скорость $$$s_i$$$.
Каждый траволатор расположен внутри отрезка $$$[0, L]$$$ и никакие два траволатора не имеют ненулевую длину пересечения. При этом траволаторы могут касаться.
Лимак хочет понять, как ему следует распределить свою энергию. Например, может быть оптимально стоять где-нибудь (или идти с низкой скоростью), чтобы сэкономить энергию и потом идти быстрее.
Изначально энергия Лимака равна $$$0$$$, и она никогда не должна падать ниже этого значения. В каждый момент он может идти со скоростью $$$v$$$ в диапазоне $$$[0, 2]$$$, и это будет стоить ему $$$v$$$ энергии. Также его энергия постоянно пополняется со скоростью $$$1$$$ единица энергии в секунду. Таким образом, если он идёт со скоростью $$$v$$$, его энергия растёт со скоростью $$$(1-v)$$$. Обратите внимание, что негативный рост означает убывание энергии.
В частности, Лимак может идти со скоростью $$$1$$$, и это никак не будет влиять на его уровень энергии, а если он будет идти со скорость $$$0.77$$$, то энергия будет расти на $$$0.23$$$.
Лимак может выбирать свою скорость произвольным образом (любое вещественное число в диапазоне $$$[0, 2]$$$) в каждый момент времени (в том числе в моменты, когда он находится в нецелых позициях). Всё происходит непрерывно (не дискретно).
За какое минимальное время Лимак сможет добраться из $$$0$$$ в $$$L$$$?
Первая строка содержит целые числа $$$n$$$ и $$$L$$$ ($$$1 \le n \le 200\,000$$$, $$$1 \le L \le 10^9$$$), число траволаторов и расстояние, которое нужно пройти.
Каждая из следующих $$$n$$$ строк содержит целые числа $$$x_i$$$, $$$y_i$$$ и вещественное число $$$s_i$$$ ($$$0 \le x_i < y_i \le L$$$, $$$0.1 \le s_i \le 10.0$$$). Значение $$$s_i$$$ дано с не более, чем $$$9$$$ знаками после запятой.
Гарантируется, что никакие два траволатора не имеют пересечения ненулевой длины. Траволаторы перечислены слева направо. Иначе говоря, $$$y_i \le x_{i + 1}$$$ при $$$1 \le i \le n - 1$$$.
Выведите одно вещественное число — минимальное время, которое нужно чтобы достичь $$$L$$$. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить $$$10^{-9}$$$.
1 5 0 2 2.0
3.000000000000
1 5 2 4 0.91
3.808900523560
3 1000 0 990 1.777777 995 996 1.123456789 996 1000 2.0
361.568848429553
Картинка изображает первые два примера. В первом примере есть траволатор из $$$0$$$ в $$$2$$$ скорости $$$2.0$$$, а Лимак хочет попасть в точку $$$5$$$. Во втором примере есть траволатор из $$$2$$$ в $$$4$$$ скорости $$$0.91$$$.
В первом примере, одна из оптимальных стратегий выглядит следующим образом.
- Добраться из $$$0$$$ в $$$2$$$ просто стоя на траволаторе. Траволатор едет со скоростью $$$2$$$, значит понадобится всего $$$1$$$ секунда времени и энергия увеличится на $$$1$$$.
- Добраться из $$$2$$$ в $$$4$$$ идя со скоростью $$$2$$$ в течении $$$1$$$ секунды. За эту $$$1$$$ секунду уровень энергии понизится до $$$0$$$.
- Добраться из $$$4$$$ в $$$5$$$ идя со скоростью $$$1$$$. На это понадобится $$$1$$$ секунда и уровень энергии будет равен $$$0$$$ всё это время.
Тем самым общее время равно $$$1 + 1 + 1 = 3$$$.
