ژان، برای برخی مسائل کاری به ایران آمده است و حال می‌خواهد برای دیدن همسرش، سابیرا، به قزاقستان برگردد. او، برای اطمینان از امنیت پرواز، تنها از پروازهای شرکت «کلم» استفاده می‌کند. پروازهای این شرکت همیشه دقیقا در زمان اعلام شده شروع می‌شوند اما ممکن است زمان فرود آن‌ها با احتمال مشخصی به تاخیر بیفتد. البته با وجود آن‌که این احتمال در مشخصات پرواز آمده است، رخ دادن تاخیر، پس از آغاز پرواز مشخص می‌شود.

به همین دلیل، او تصمیم گرفته است که در هر فرودگاه پرواز بعدی خود را انتخاب کند. یعنی ژان در ابتدا تنها پرواز اول خود را انتخاب می‌کند و سپس پس از رسیدن به مقصد(که ممکن است با یا بدون تاخیر صورت بگیرد) پرواز بعدی خود را انتخاب می‌کند و این‌کار را ادامه می‌دهد تا به قزاقستان برسد. فرض کنید تعویض پرواز بلافاصله انجام می‌شود یعنی اگر زمان شروع پرواز هواپیمای دوم دقیقا در زمان فرود پرواز هواپیمای اول باشد، ژان می‌تواند از آن استفاده کند.

توجه کنید که ممکن است رسیدن به قزاقستان همیشه ممکن نباشد. از آن‌جا که ژان می‌خواهد در سریع‌ترین زمان ممکن به قزاقستان برسد، پروازهای خود را طوری انتخاب می‌کند که اولا حتما در هر شرایطی به قزاقستان برسد و دوما امید ریاضی زمان رسیدن او از ایران به قزاقستان کمینه شود.

برنامه‌ای بنویسید که با داشتن مشخصات پروازها، امید ریاضی زمان رسیدن او از ایران به قزاقستان را محاسبه کند. در صورتی که ژان نمی‌تواند طوری پروازهای خود را انتخاب کند که تحت هر شرایطی به قزاقستان برسد، برنامه‌ی شما باید عدد $-1$ را به عنوان جواب خروجی دهد.

لازم به ذکر است پروازهای شرکت کلم تنها بین $n$ فرودگاه انجام می‌گیرد که با شماره‌های $1$ تا $n$ شماره‌گذاری شده‌اند. فرودگاه مبدا در ایران، فرودگاه شماره‌ی $1$ و فرودگاه مقصد در قزاقستان، فرودگاه شماره‌ی $n$ است. توجه کنید که ممکن است دو پرواز از یک فرودگاه به فرودگاه دیگر باشد.

در خط اول ورودی، دو عدد $n$ و $m$، که به ترتیب تعداد فرودگاه‌ها و تعداد پروازهای شرکت کلم هستند، آمده‌اند. در هر یک از $m$ خط بعدی،‌ مشخصات یک پرواز آمده است که شامل شش عدد صحیح است. این اعداد به ترتیب از چپ به راست نشان‌دهنده‌ی موارد زیر هستند:

• $a$: شماره‌ی فرودگاه مبدا پرواز
• $b$: شماره‌ی فرودگاه مقصد پرواز
• $s$: زمان آغاز پرواز
• $l$: طول پرواز در حالت عادی
• $p$: درصد احتمال تاخیر پرواز
• $d$: مدت زمان تاخیر در صورت رخ دادن آن

در تنها خط خروجی، اگر ژان نمی‌تواند پروازهای خود را طوری انتخاب کند که حتما به قزاقستان برسد عدد $-1$ را چاپ کنید. در غیر این‌صورت امید ریاضی کمینه برای رسیدن از ایران به قزاقستان را چاپ کنید. پاسخ شما در صورتی درست محسوب می‌شود که خطای آن نسبت به پاسخ صحیح کمتر از $10^{-6}$ باشد.

• زیرمسئله اول (۹ نمره): $m = n - 1$ و پرواز $i (1 \le i \le m)$م از فرودگاه $i$ به $i + 1$ است.
• زیرمسئله دوم (۱۵ نمره): $d = 0$
• زیرمسئله سوم (۲۸ نمره):$ n \le 100, m \le 2000 $
• زیرمسئله چهارم(۴۸ نمره): بدون محدودیت اضافی

• $2 \le n \le 2 \times 10^5$
• $0 \le m \le 5 \times 10^5$
• $1 \le a, b \le n$
• $a \neq b$
• $1 \le s, l \le 10^9$
• $0 \le d \le 10^9$
• $0 \le p \le 100$

در ورودی نمونه‌ی اول، تنها یک پرواز از فرودگاه شماره‌ی $1$ وجود دارد(پرواز اول). این پرواز به احتمال $80$ درصد بدون تاخیر به مقصد خود می‌رسد که در این صورت ژان با انتخاب پرواز دوم می‌تواند در زمان $21$ به قزاقستان برسد. در غیر این‌صورت این پرواز در زمان $16$ به فرودگاه شماره‌ی $2$ می‌رسد و ژان باید چهار دقیقه منتظر شود تا پرواز سوم آغاز شود و در این صورت او در زمان $27$ به مقصد می‌رسد. در نتیجه پاسخ مسئله برابر است با:

$$\frac{80}{100} \times 21 + \frac{20}{100} \times 27 = 22.2$$

• سوال بعد
• سوال قبل