Ваш самолет вылетает на финал ICPC в ближайшее время, и единственный способ добраться до аэропорта --- на автобусе. К сожалению, некоторые водители автобусов подумывают о забастовке, поэтому Вы не знаете, сможете ли добраться до аэропорта вовремя. Ваша цель --- спланировать свое путешествие таким образом, чтобы максимизировать вероятность успеть на самолет. Перед Вами расположена подробная карта города, на которой отмечены все автовокзалы. Вы находитесь на станции $0$, а аэропорт --- на станции $1$. У Вас также есть полное расписание того, когда каждый автобус покидает свою начальную станцию и прибывает на станцию назначения. Кроме того, для каждого автобуса Вы знаете вероятность того, что он действительно будет ходить по расписанию, а не что его водитель объявит забастовку и выведет автобус из эксплуатации. Предположим, что все эти события независимы. То есть вероятность того, что данный автобус будет работать по плану, не изменится, если Вы знаете, работает ли какой-либо другой автобус по плану. Если Вы приедете раньше времени отправления автобуса, то сможете сесть на этот автобус. Но если Вы приедете точно ко времени отправления, то Вам не хватит времени чтобы сесть в автобус. Вы не можете заранее проверить, будет ли данный автобус курсировать по плану --- Вы узнаете это только тогда, когда попытаетесь сесть в автобус. Если со станции одновременно отправляются два или более автобусов, можно попробовать сесть только на один из них. \includegraphics{https://static.eolymp.com/content/0n/0nk2ftql016q921rnig7va0gs0.gif} Рассмотрим расписание движения автобусов, представленное на рисунке А.1. В нем перечислены станции отправления и назначения нескольких автобусных маршрутов, а также время отправления и прибытия. Рядом с некоторыми из них Вы написали вероятность того, что этот маршрут будет работать. Автобусные маршруты, рядом с которыми не написана вероятность, имеют 100\% вероятность выполнения. Вы можете попробовать сесть на первый попавшийся автобус. Если он поедет, он доставит Вас прямо в аэропорт, и Вы можете не беспокоиться. Если этого не происходит, все становится сложнее. Вы можете сесть на второй автобус до станции $2$. Он наверняка уедет, но Вы опоздаете на третий по списку автобус, который доставил бы Вас в аэропорт вовремя. Четвертый указанный автобус, который Вы можете поймать, имеет вероятность фактического движения всего лишь $0,1$. Это плохая ставка, поэтому лучше остаться на станции $0$ и дождаться пятого автобуса из списка. Если Вы его поймаете, то сможете попытаться сесть на шестой по списку автобус, идущий в аэропорт; если он не работает, у Вас все равно есть шанс вернуться на станцию $0$ и сесть на последний указанный автобус прямо в аэропорт. \InputFile В первой строке записаны два целых числа $m~(1 \le m \le 10^6)$ и $n~(2 \le n \le 10^6)$, обозначающие количество автобусов и количество станций в городе. В следующей строке записано одно целое число $k~(1 \le k \le 10^{18})$, обозначающее время, к которому Вы должны прибыть в аэропорт. Каждая из следующих $m$ строк описывает один автобусный маршрут. В каждой строке записаны целые числа $a$ и $b~(0 \le a, b < n, a \ne b)$, обозначающие начальную и конечную станции автобуса. Далее идут целые числа $s$ и $t~(0 \le s < t \le k)$, задающие время отправления со станции $a$ и время прибытия на станцию $b$. Последнее значение в строке --- $p~(0 \le p \le 1$, не более $10$ десятичных цифр), которое обозначает вероятность того, что автобус будет работать по плану. \OutputFile Выведите вероятность того, что Вы успеете на свой самолет, предполагая, что Вы следуете оптимальному образу действий. Ваш ответ должен быть правильным с точностью до $10^{-6}$.