Затримки поїздів
Минулого року деякі судді намагалися дістатися до NWERC’10 поїздом, але це обернулося великою катастрофою: дорогою туди пожежа в диспетчерській викликала величезні затримки, а на зворотному шляху поїзди в Бремені затрималися через загрозу терористичного акту в Гамбурзі. Ці значні затримки спричинили подальші збої в розкладі поїздів, тому виникло питання, які поїзди обрати: чи краще сісти на повільний регіональний поїзд зараз, чи почекати на міжміський, який може затриматися?
Цього року судді заздалегідь спланували свою подорож і ретельно проаналізували розклад поїздів. Вони навіть відстежували частоту та тривалість затримок. Тепер, маючи всю цю інформацію, вони прагнуть подорожувати якомога швидше, мінімізуючи очікувану тривалість подорожі. Чи можете ви їм допомогти?
Для кожного залізничного сполучення судді точно знають запланований час відправлення, тривалість поїздки та ймовірність затримки прибуття. Ви можете припустити, що ймовірності затримок є незалежними, і що судді можуть змінювати свій маршрут у міру просування, залежно від затримок, які вже сталися. Поїзди завжди відправляються вчасно, але можуть прибути із запізненням, і судді не знають про можливу затримку до посадки. Суддям не потрібно часу на пересадку, тому вони можуть сісти на поїзд, що відправляється в момент їх прибуття.
Судді можуть обрати час свого початкового відправлення за бажанням, і вони прагнуть мінімізувати очікувану тривалість своєї загальної подорожі.
Вхідні дані
На першому рядку міститься позитивне ціле число: кількість тестових випадків, не більше 100. Далі для кожного тестового випадку:
один рядок з місцем відправлення та призначення суддів, вони різні.
один рядок з цілим числом n (1 ≤ n ≤ 1000): кількість залізничних сполучень.
n рядків, кожен описує залізничне сполучення: - місце відправлення та призначення цього сполучення, вони різні.
ціле число m (0 ≤ m ≤ 59), час відправлення в хвилинах після кожної повної години.
ціле число t (1 ≤ t ≤ 300), стандартний час подорожі (без урахування затримок).
ціле число p (0 ≤ p ≤ 100), ймовірність затримки у відсотках.
ціле число d (1 ≤ d ≤ 120), максимальна затримка в хвилинах.
Усі назви місць подані як рядки з великих і малих літер алфавіту, довжиною не більше 20. Якщо поїзд затримується, то тривалість затримки буде цілим числом хвилин і рівномірно розподілена в діапазоні [1, d].
Вихідні дані
Для кожного тестового випадку:
один рядок з числом з плаваючою комою: мінімальна очікувана тривалість загальної подорожі в хвилинах.
Це число повинно бути точним до 10^(-6) відносної або абсолютної точності. Виведіть IMPOSSIBLE, якщо місце призначення недосяжне.