Встигнути на літак

Ваш літак скоро вилітає на фінал ICPC, і єдиний спосіб дістатися до аеропорту — це автобус. На жаль, деякі водії автобусів планують страйк, тому Ви не впевнені, чи встигнете вчасно. Ваше завдання — спланувати подорож так, щоб максимізувати ймовірність встигнути на літак.

У Вас є детальна карта міста з усіма автовокзалами. Ви знаходитесь на станції $0$, а аеропорт розташований на станції $1$. Також у Вас є розклад, який показує, коли кожен автобус відправляється зі своєї початкової станції і прибуває на кінцеву. Крім того, для кожного автобуса відома ймовірність, що він буде працювати за розкладом, а не буде зупинений через страйк. Всі ці події незалежні, тобто ймовірність роботи автобуса не залежить від інших автобусів.

Якщо Ви прибудете раніше часу відправлення автобуса, Ви зможете сісти на нього. Але якщо прибудете точно в момент відправлення, сісти не встигнете. Ви не можете заздалегідь дізнатися, чи працює автобус за розкладом — це стане відомо лише під час посадки. Якщо з однієї станції одночасно відправляються кілька автобусів, Ви можете спробувати сісти лише на один з них.

Розгляньмо розклад автобусів на рисунку А.1. Він містить станції відправлення та прибуття кількох маршрутів, а також часи відправлення і прибуття. Поруч з деякими маршрутами вказана ймовірність їх виконання. Маршрути без вказаної ймовірності мають 100

Вхідні дані

Перший рядок містить два цілі числа $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$ десяткових знаків), яке позначає ймовірність, що автобус буде працювати за розкладом.

Вихідні дані

Виведіть ймовірність того, що Ви встигнете на свій літак, дотримуючись оптимальної стратегії. Ваша відповідь повинна бути точною до $10^{-6}$.

Приклади