Подорож до Греції#7706
Тим давно мріяв відвідати Грецію. Він вже придбав квитки до Афін і назад. У Тіма є список історичних місць, які він хоче відвідати, наприклад Олімпія і Дельфи. Проте через останні політичні події в Греції громадський транспорт став менш зручним. Щоб жителі були задоволені своїм новим урядом, були створені маршрути малої дальності для автобусів і поїздів. Вони розвозять громадян по районах на роботу або до лікаря. При цьому далекі поїзди, які були б зручні для туристів, закриті, оскільки вони занадто дорогі. Це ускладнює подорож для таких людей, як Тим, який любить пересуватися на поїзді. Більше того, він вже придбав туристичну карту Греції, яка робить усі поїзди та автобуси для нього безкоштовними.
Довжина туру Тіма дорівнює .
Незважаючи на закриття залізничних ліній, Тим все ще хоче подорожувати по Греції. Хоча локальні маршрути автобусів і поїздів достатньо повільні, він хоче дізнатися, чи зможе він відвідати всі свої улюблені місця за час перебування в країні. Його графік буде щільним, але він має можливість придбати єдиний квиток на грецьку службу таксі, яка доставить його з будь-якої точки країни до будь-якої іншої за фіксований час.
Для простоти припустимо, що Тіму ніколи не доведеться чекати наступного автобуса або поїзда на станції. Визначте, чи зможе Тим відвідати всі місця, і якщо так, чи потрібне йому використання таксі.
Перша строка містить п’ять цілих чисел n, p, m, g і , де
n~(1 \le n \le 2 \cdot 10^4) — кількість місць у Греції,
p~(1 \le p \le 15) — кількість місць, які Тим хоче відвідати,
m~(1 \le m \le 10^5) — кількість транспортних сполучень,
g~(1 \le g \le 10^5) — загальний час перебування Тіма в Греції,
t~(1 \le t \le 500) — час поїздки на таксі.
Наступні рядків містять по два числа x_i та y_i~(0 \le x_i < n, 1 \le y_i \le 500) — місце, яке Тим хоче відвідати, та час відвідування. Всі місця x_i різні.
Кожен з наступних рядків описує одне з’єднання і містить три числа s_i, d_i та w_i~(0 \le s_i, d_i < n, 1 \le w_i \le 500) — початкове і кінцеве місце, а також час переміщення між ними. Усі з’єднання двосторонні. Подорож Тіма починається і закінчується в Афінах, місті з номером .
Виведіть одне з трьох повідомлень:
impossible — якщо Тим не зможе відвідати всі місця за відведений час;
possible without taxi — якщо він зможе відвідати всі місця без використання таксі;
possible with taxi — якщо для відвідування всіх місць потрібно буде скористатися службою таксі.
Приклад 1