비행기 잡기

ICPC 결승전으로 가는 비행기가 곧 출발한다. 공항까지 가는 방법은 버스뿐인데, 일부 버스 기사가 파업을 검토하고 있어서 공항에 제시간에 닿을지 확신할 수 없다. 비행기를 탈 확률이 가장 커지도록 이동 계획을 세워라.

도시의 버스 정류장이 모두 표시된 지도가 있다. 당신은 0번 정류장에 있고 공항은 1번 정류장이다. 각 버스가 출발 정류장을 떠나는 시각과 도착 정류장에 닿는 시각을 적은 시간표도 있다. 버스마다 기사가 파업하지 않고 예정대로 운행할 확률도 알고 있다. 이 사건들은 서로 독립이다. 즉, 어떤 버스가 운행하는지 알아내도 다른 버스가 운행할 확률은 달라지지 않는다.

버스가 출발하는 시각보다 먼저 정류장에 닿으면 그 버스로 갈아탈 수 있다. 출발 시각과 똑같은 시각에 닿으면 시간이 모자라 타지 못한다. 어떤 버스가 예정대로 운행하는지는 미리 확인하지 못하고, 그 버스에 타려고 해야 비로소 알게 된다. 그래서 한 정류장에서 같은 시각에 버스가 두 대 이상 떠나면 그중 한 대만 시도할 수 있다.

그림 1: 첫 번째 예제의 버스 시간표.

그림 1의 시간표를 보자. 노선마다 출발 정류장과 도착 정류장, 출발 시각과 도착 시각이 적혀 있고, 일부 노선 옆에는 그 노선이 운행할 확률이 적혀 있다. 확률이 적히지 않은 노선은 반드시 운행한다. 먼저 첫째 노선을 시도할 수 있다. 그 버스가 운행하면 공항까지 곧장 데려다주므로 더 걱정할 일이 없다. 운행하지 않으면 상황이 까다로워진다. 둘째 노선을 타고 2번 정류장으로 갈 수도 있다. 이 버스는 반드시 떠나지만, 그러면 공항에 제때 데려다줄 셋째 노선에 늦는다. 그래도 탈 수 있는 넷째 노선은 운행할 확률이 0.1뿐이다. 승산이 낮으니 0번 정류장에 남아 다섯째 노선을 기다리는 편이 낫다. 다섯째 노선을 타면 공항으로 가는 여섯째 노선을 시도할 수 있고, 그 버스가 운행하지 않아도 0번 정류장으로 돌아와 마지막 노선을 타고 공항으로 갈 기회가 남는다.

첫째 줄에 버스의 수 $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$), 정류장 $a$에서 떠나는 시각 $s$와 정류장 $b$에 닿는 시각 $t$ ($0 \le s < t \le k$), 그 버스가 예정대로 운행할 확률 $p$ ($0 \le p \le 1$, 소수점 아래 최대 10자리)가 순서대로 주어진다.

최적으로 움직였을 때 비행기를 탈 확률을 한 줄에 출력한다. 소수점 아래 여섯째 자리까지 반올림해 항상 여섯 자리로 적는다. 확률이 정확히 $0.7$이면 0.700000을 출력한다. 여섯째 자리 반올림 경계에 정답이 놓이는 입력은 주어지지 않는다.