Maximizing Flight Catch Probability

Your plane to the ICPC Finals departs soon, and the only way to get to the airport is by bus. Unfortunately, some bus drivers may go on strike, so you are not sure if you can reach the airport on time. You have a detailed map of the city with all bus stations. You are currently at station \(0\) and the airport is at station \(1\). You also have a schedule of all buses. For each bus, you know its start station, destination station, departure time, arrival time, and the probability \(p\) (in \(0 \le p \le 1\)) that it runs as scheduled. If a bus does not run (because its driver goes on strike), you will only know at the time of departure. All events are independent.

If you arrive strictly before the departure time of a bus, you can attempt to take that bus. However, if you arrive exactly at the departure time, you cannot catch it. Moreover, if two or more buses leave a station at the same time, you can only try to board one of them. Your goal is to plan a strategy (possibly involving transfers and retries) to maximize the probability of reaching station \(1\) (the airport).

When you try to board a bus departing from station \(i\) at time \(d\) to station \(j\) arriving at time \(a\) with probability \(p\), the expected probability of success is computed as:

[ E = p \times f(j, a) + (1-p) \times f(i, d), ]

where \(f(i, t)\) is the maximum probability of reaching the airport when you are at station \(i\) at time \(t\). You start at station \(0\) at time \(0\) and if you ever reach station \(1\), you have successfully caught your plane (i.e. \(f(1, t)=1\) for any \(t\)). If no further bus can be taken from a station, the probability is \(0\). Find the maximum probability of catching your plane.

Note: All times are given as integers. You can only board a bus if your current time is strictly less than its departure time.

inputFormat

The first line contains a single integer \(n\) (\(1 \leq n \leq 1000\)), the number of bus routes.

Each of the next \(n\) lines contains five values:

• \(s\): the start station (an integer)
• \(d\): the destination station (an integer)
• \(t_{depart}\): the departure time (an integer)
• \(t_{arrive}\): the arrival time (an integer, with \(t_{arrive} > t_{depart}\))
• \(p\): the probability (a real number between 0 and 1) that the bus will run as scheduled. If a bus always runs, \(p = 1.0\).

You start at station \(0\) at time \(0\) and need to reach station \(1\) (the airport) by taking one or more buses.

outputFormat

Output the maximum probability of reaching the airport. Your answer will be considered correct if its absolute error does not exceed \(10^{-4}\). Print the answer as a floating point number with at least 4 decimal places.

sample

4
0 2 10 20 0.9
2 1 25 35 1.0
0 1 15 30 0.5
0 1 20 25 0.8

0.9900