{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eYour plane to the ICPC Finals departs in a short time, and\n the only way to get to the airport is by bus. Unfortunately,\n some of the bus drivers are considering going on strike, so you\n do not know whether you can get to the airport on time. Your\n goal is to plan your journey in such a way as to maximize the\n probability of catching your plane.\u003c/p\u003e\n \u003cp\u003eYou have a detailed map of the city, which includes all the\n bus stations. You are at station \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e and the airport is at station\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e. You also have a\n complete schedule of when each bus leaves its start station and\n arrives at its destination station. Additionally, for each bus\n you know the probability that it is actually going to run as\n scheduled, as opposed to its driver going on strike and taking\n the bus out of service. Assume all these events are\n independent. That is, the probability of a given bus running as\n planned does not change if you know whether any of the other\n buses run as planned.\u003c/p\u003e\n \u003cp\u003eIf you arrive \u003cem\u003ebefore\u003c/em\u003e the departure time of a bus,\n you can transfer to that bus. But if you arrive exactly at the\n departure time, you will not have enough time to get on the\n bus. You cannot verify ahead of time whether a given bus will\n run as planned – you will find out only when you try to get on\n the bus. So if two or more buses leave a station at the same\n time, you can try to get on only one of them.\u003c/p\u003e\n \u003cdiv id\u003d\"fig:catch\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/7d3e02ade68a88ce140142ecbdedba0a?v\u003d1715425027\" alt\u003d\"\\includegraphics[width\u003d0.5\\textwidth ]{catch2}\" style\u003d\"width:50.00%\"\u003e\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: Bus schedule corresponding to Sample\n Input 1.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n \u003cp\u003eConsider the bus schedule shown in Figure\u0026nbsp;1. It lists\n the start and destination stations of several bus routes along\n with the departure and arrival times. You have written next to\n some of these the probability that that route will run. Bus\n routes with no probability written next to them have a\n \u003cspan class\u003d\"tex2jax_process\"\u003e$100\\% $\u003c/span\u003e chance of\n running. You can try catching the first listed bus. If it runs,\n it will take you straight to the airport, and you can stop\n worrying. If it does not, things get more tricky. You could get\n on the second listed bus to station \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e. It is certain to leave, but you\n would be too late to catch the third listed bus which otherwise\n would have delivered you to the airport on time. The fourth\n listed bus – which you can catch – has only a \u003cspan class\u003d\"tex2jax_process\"\u003e$0.1$\u003c/span\u003e probability of actually running.\n That is a bad bet, so it is better to stay at station\n \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e and wait for the fifth\n listed bus. If you catch it, you can try to get onto the sixth\n listed bus to the airport; if that does not run, you still have\n the chance of returning to station 0 and catching the last\n listed bus straight to the airport.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line of input contains two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\le m \\le 10^6$\u003c/span\u003e) and \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$2\n \\le n \\le 10^6$\u003c/span\u003e), denoting the number of buses and the\n number of stations in the city. The next line contains one\n integer \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le k \\le 10^{18}$\u003c/span\u003e), denoting the\n time by which you must arrive at the airport.\u003c/p\u003e\n \u003cp\u003eEach of the next \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e\n lines describes one bus. Each line contains integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0\n \\le a, b \u0026lt; n$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$a \\ne\n b$\u003c/span\u003e), denoting the start and destination stations for the\n bus. Next are integers \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e\n and \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\le s \u0026lt; t \\le k$\u003c/span\u003e), giving the\n departure time from station \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e and the arrival time at station\n \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e. The last value on the\n line is \u003cspan class\u003d\"tex2jax_process\"\u003e$p$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\le p \\le 1$\u003c/span\u003e, with at most\n \u003cspan class\u003d\"tex2jax_process\"\u003e$10$\u003c/span\u003e digits after the\n decimal point), which denotes the probability that the bus will\n run as planned.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eDisplay the probability that you will catch your plane,\n assuming you follow an optimal course of action. Your answer\n must be correct to within an absolute error of \u003cspan class\u003d\"tex2jax_process\"\u003e$10^{-6}$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e8 4\n1000\n0 1 0 900 0.2\n0 2 100 500 1.0\n2 1 500 700 1.0\n2 1 501 701 0.1\n0 3 200 400 0.5\n3 1 500 800 0.1\n3 0 550 650 0.9\n0 1 700 900 0.1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.3124\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 2\n2\n0 1 0 1 0.5\n0 1 0 1 0.5\n0 1 1 2 0.4\n0 1 1 2 0.2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.7\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}