Подорож до Греції
Тім давно мріяв відвідати Грецію. Він уже придбав квитки на рейси до та з Афін. У Тіма є список історичних місць, які він хоче побачити, таких як Олімпія та Дельфи. Однак через останні політичні зміни в Греції громадський транспорт став менш зручним. Щоб задовольнити місцевих жителів, були створені короткі автобусні та залізничні маршрути, які перевозять людей до роботи або лікарні. Водночас далекі потяги, які підходять для туристів, були скасовані через їх високу вартість. Це створює труднощі для таких мандрівників, як Тім, який любить подорожувати потягом. До того ж, він уже придбав картку, яка дозволяє йому безкоштовно користуватися всіма потягами та автобусами в Греції.
Довжина туру Тіма становить 18.
Незважаючи на закриття залізничних ліній, Тім все ще прагне подорожувати по Греції. Хоча місцеві автобуси та потяги рухаються повільно, він хоче дізнатися, чи зможе відвідати всі заплановані місця під час свого перебування. Його графік буде напруженим, але у нього є додаткові кошти на єдиний квиток для грецької служби таксі, яка обіцяє доставити його з будь-якої точки Греції в іншу за певний час.
Для спрощення вважатимемо, що Тім ніколи не чекатиме на наступний автобус чи потяг на станції. Чи зможе він відвідати всі місця, і якщо так, чи знадобиться йому скористатися таксі?
Вхідні дані
Перша строка містить п'ять цілих чисел n, p, m, g і t, де n - кількість місць у Греції, p - кількість місць, які хоче відвідати Тім, m - кількість з'єднань, g - загальний час перебування в Греції, і t - час поїздки на таксі (1 ≤ n ≤ 2 * 10^4, 1 ≤ p ≤ 15, 1 ≤ m, g ≤ 10^5, 1 ≤ t ≤ 500).
Кожен з наступних p рядків задає два числа p[i] і t[i] (0 ≤ p[i] < n, 1 ≤ t[i] ≤ 500) - місце, яке Тім хоче відвідати, і час, необхідний для відвідування цього місця. Всі місця p[i] різні.
Кожен з наступних m рядків описує одне з'єднання і містить три числа s[i], d[i] і t[i] (0 ≤ s[i], d[i] < n, 1 ≤ t[i] ≤ 500), де s[i] і d[i] - початкове і кінцеве місце, а t[i] - час пересування між ними.
Всі з'єднання двонапрямні. Подорож Тіма починається і закінчується в Афінах - місті з номером 0.
Вихідні дані
Виведіть "impossible", якщо Тім не зможе відвідати всі місця за відведений час, "possible without taxi", якщо він зможе відвідати місця без використання таксі, або "possible with taxi", якщо для відвідування всіх місць потрібно скористатися таксі.