Qatar qatarlarının gecikmələri#4017
Keçən il bəzi hakimlər NWERC’10-a qatarla səyahət etməyə çalışdılar. Bu, böyük bir fəlakətə çevrildi: yolda idarəetmə otağında baş verən yanğın ciddi gecikmələrə səbəb oldu, geri dönüşdə isə Hamburqda terror təhlükəsi səbəbindən Bremen qatarları gecikdi. Təbii ki, bu böyük gecikmələr qatar cədvəlində digər gecikmələrə də yol açdı. Beləliklə, böyük sual ortaya çıxdı: indi bu yavaş regional qatarı götürmək daha yaxşıdır, yoxsa gecikmə ehtimalı yüksək olan həmin şəhərlərarası qatarı gözləmək?
Bu il hakimlər əvvəlcədən planlaşdırıblar və qatar cədvəlini diqqətlə təhlil ediblər. Onlar hətta qatarların nə qədər tez-tez və nə qədər gecikdiyini izləyiblər. İndi bütün bu məlumatlara sahib olduqlarına görə, mümkün qədər tez səyahət etmək və səfərin gözlənilən müddətini minimuma endirmək istəyirlər. Onlara kömək edə bilərsinizmi?
Hər bir qatar əlaqəsi üçün hakimlər onun planlaşdırılmış yola düşmə vaxtını və müddətini, həmçinin təyinat yerinə çatmasının gecikmə ehtimalını dəqiq bilirlər. Gecikmə ehtimallarının müstəqil olduğunu və hakimlərin artıq qarşılaşdıqları hər hansı gecikmələrdən asılı olaraq marşrutlarını dəyişdirə biləcəyini fərz edə bilərsiniz. Qatarlar həmişə vaxtında yola düşür, lakin gecikə bilər və hakimlər qatara minənə qədər onun gəlişinin gecikib-gecikməyəcəyini bilmirlər. Hakimlər qatarları dəyişmək üçün vaxt itirmirlər, buna görə də bir yerə çatdıqları zaman yola düşən əlaqəli qatarı götürə bilərlər.
Hakimlər ilkin yola düşmə vaxtını istədikləri kimi seçə bilərlər və ümumi səfərin gözlənilən müddətini minimuma endirmək istəyirlər.
Birinci sətirdə müsbət tam ədəd: test halların sayı, ən çox 100. Bundan sonra hər test halı üçün:
bir sətir hakimlərin mənşəyi və təyinat yeri, bunlar fərqlidir.
bir sətir tam ədəd n (1 ≤ n ≤ 1000): qatar əlaqələrinin sayı.
n sətir, hər biri qatar əlaqəsini təsvir edir: - bu əlaqənin mənşəyi və təyinat yeri, bunlar fərqlidir.
tam ədəd m (0 ≤ m ≤ 59), hər tam saatdan sonra dəqiqələrdə yola düşmə vaxtı.
tam ədəd t (1 ≤ t ≤ 300), standart səfər müddəti (gecikmələr nəzərə alınmadan).
tam ədəd p (0 ≤ p ≤ 100), gecikmə ehtimalı faizlə.
tam ədəd d (1 ≤ d ≤ 120), maksimum gecikmə dəqiqələrdə.
Bütün yer adları ən çox 20 uzunluğunda böyük və kiçik hərflərlə verilmiş simvollardır. Əgər qatar gecikərsə, gecikmə müddəti dəqiqələrdə tam ədəd olacaq və [1, d] aralığında bərabər paylanacaq.
Hər test halı üçün:
bir sətir üzərində ondalık nöqtə ilə göstərilən ədəd: ümumi səfərin minimum gözlənilən müddəti dəqiqələrdə.
Bu ədəd 10^(-6) nisbi və ya mütləq dəqiqliklə dəqiq olmalıdır. Əgər təyinat yerinə çatmaq mümkün deyilsə, əvəzinə MÜMKÜN DEYİL çıxarın.
Nümunə 1