Путешествие в Грецию
В течение долгого времени Тим хотел посетить Грецию. Он уже приобрел свой рейс в и из Афин. У Тима есть список исторических мест, которые он хочет посетить- например Олимпии и Делфи. Однако в связи с последними политическими событиями в Греции общественный транспорт стал немного сложнее. Для того чтобы греки стали счастливыми и довольными своим новым правительством, были созданы автобусные и железнодорожные маршруты малой дальности. Они развозят граждан своих районов на работу или к врачу. В то же время дальние поезда, которые идеально подходят для туристов, были закрыты, поскольку они являются слишком дорогими. Это плохо для таких людей как Тим, который очень любит путешествовать на поезде. Более того, он уже приобрел карточку Греции для перевозки пассажиров, которая делает все поезда и автобусы для него бесплатными.
Длина тура Тима равна 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" если для посещения всех мест следует воспользоваться службой такси.